New Trends in Discrete and Computational Geometry

1. Front Matter

   Pages I-XI

   PDF

2. Introduction

   • János Pach

   Pages 1-7

3. Combinatorics and Algorithms of Arrangements

   • Leonidas Guibas, Micha Sharir

   Pages 9-36

4. Backwards Analysis of Randomized Geometric Algorithms

   • Raimund Seidel

   Pages 37-67

5. Epsilon-Nets and Computational Geometry

   • Jiří Matoušek

   Pages 69-89

6. Complexity of Polytope Volume Computation

   • Leonid Khachiyan

   Pages 91-101

7. Allowable Sequences and Order Types in Discrete and Computational Geometry

   • Jacob E. Goodman, Richard Pollack

   Pages 103-134

8. Hyperplane Approximation and Related Topics

   • Nikolai M. Korneenko, Horst Martini

   Pages 135-161

9. Geometric Transversal Theory

   • Jacob E. Goodman, Richard Pollack, Rephael Wenger

   Pages 163-198

10. Hadwiger-Levi’s Covering Problem Revisited

    • Károly Bezdek

    Pages 199-233

11. Geometric and Combinatorial Applications of Borsuk’s Theorem

    • Imre Bárány

    Pages 235-249

12. A Survey of Recent Results in the Theory of Packing and Covering

    • Gábor Fejes Tóth, Wlodzimierz Kuperberg

    Pages 251-279

13. Recent Developments in Combinatorial Geometry

    • W. Moser, J. Pach

    Pages 281-302

14. Set Theoretic Constructions in Euclidean Spaces

    • Péter Komjáth

    Pages 303-325

15. Back Matter

    Pages 327-340

    PDF

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. The book consists of twelve chapters summarizing the most recent results and methods in discrete and computational geometry. All authors are well-known experts in these fields. They give concise and 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. Most of the methods and results discussed in the book have not appeared in any previously published monograph. 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. Apart from mathematicians working in discrete and computational geometry this book will also be of great use to computer scientists and engineers, who would like to learn about the most recent results.

• Algorithmentheorie
• Approximation von Hyperebenen
• Combinatorics
• Epsilonnetze
• Kombinatorik
• Konvexität
• Partition
• combinatorial geometry
• computational geometry
• discrete geometry
• diskrete Geometrie
• epsilon-nets
• mathematics
• robot
• robotics

• Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Hungary

  János Pach

• Courant Institute, New York University, New York, USA

  János Pach

Policies and ethics