Discrete and computational geometry are two fields which in recent years have benefitted from the interaction between mathematics and computer science. The results are applicable in areas such as motion planning, robotics, scene analysis and computer aided design. This book consists of twelve chapters summarizing the most recent results and methods in discrete and computational geometry. The authors give self-contained surveys of the most efficient combinatorical, probabilistic and topological methods that can be used to design effective geometric algorithms for the applications mentioned above. In particular, this book contains the first systematic treatment of epsilon-nets, geometric tranversal theory, partitions of Euclidean spaces and a general method for the analysis of randomized geometric algorithms.
Author(s): János Pach (auth.), János Pach (eds.)
Series: Algorithms and Combinatorics 10
Publisher: Springer Berlin Heidelberg
Year: 1993
Language: English
Pages: 349
City: Berlin; New York
Tags: Combinatorics; Geometry; Economic Theory; Math. Applications in Chemistry; Computational Intelligence
Front Matter....Pages I-XI
Introduction....Pages 1-7
Combinatorics and Algorithms of Arrangements....Pages 9-36
Backwards Analysis of Randomized Geometric Algorithms....Pages 37-67
Epsilon-Nets and Computational Geometry....Pages 69-89
Complexity of Polytope Volume Computation....Pages 91-101
Allowable Sequences and Order Types in Discrete and Computational Geometry....Pages 103-134
Hyperplane Approximation and Related Topics....Pages 135-161
Geometric Transversal Theory....Pages 163-198
Hadwiger-Levi’s Covering Problem Revisited....Pages 199-233
Geometric and Combinatorial Applications of Borsuk’s Theorem....Pages 235-249
A Survey of Recent Results in the Theory of Packing and Covering....Pages 251-279
Recent Developments in Combinatorial Geometry....Pages 281-302
Set Theoretic Constructions in Euclidean Spaces....Pages 303-325
Back Matter....Pages 327-340
