Twentieth Anniversary Volume: Discrete & Computational Geometry

1. Front Matter

   Pages 1-16

   PDF

2. There Are Not Too Many Magic Configurations

   • Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, Günter Rote

   Pages 1-14

3. Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles

   • Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir et al.

   Pages 1-21

4. Robust Shape Fitting via Peeling and Grating Coresets

   • Pankaj K. Agarwal, Sariel Har-Peled, Hai Yu

   Pages 1-21

5. Siegel’s Lemma and Sum-Distinct Sets

   • Iskander Aliev

   Pages 1-8

6. Slicing Convex Sets and Measures by a Hyperplane

   • Imre Bárány, Alfredo Hubard, Jesús Jerónimo

   Pages 1-9

7. A Centrally Symmetric Version of the Cyclic Polytope

   • Alexander Barvinok, Isabella Novik

   Pages 1-24

8. On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities

   • Saugata Basu, Thierry Zell

   Pages 1-23

9. Enumeration in Convex Geometries and Associated Polytopal Subdivisions of Spheres

   • Louis J. Billera, Samuel K. Hsiao, J. Scott Provan

   Pages 1-15

10. Isotopic Implicit Surface Meshing

    • Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter

    Pages 1-20

11. Line Transversals to Disjoint Balls

    • Ciprian Borcea, Xavier Goaoc, Sylvain Petitjean

    Pages 1-16

12. Norm Bounds for Ehrhart Polynomial Roots

    • Benjamin Braun

    Pages 1-3

13. Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

    • Otfried Cheong, Xavier Goaoc, Andreas Holmsen, Sylvain Petitjean

    Pages 1-19

14. Grid Vertex-Unfolding Orthogonal Polyhedra

    • Mirela Damian, Robin Flatland, Joseph O’Rourke

    Pages 1-26

15. Empty Convex Hexagons in Planar Point Sets

    • Tobias Gerken

    Pages 1-34

16. Affinely Regular Polygons as Extremals of Area Functionals

    • Paolo Gronchi, Marco Longinetti

    Pages 1-25

17. Improved Output-Sensitive Snap Rounding

    • John Hershberger

    Pages 1-21

18. Generating All Vertices of a Polyhedron Is Hard

    • Leonid Khachiyan, Endre Boros, Konrad Borys, Vladimir Gurvich, Khaled Elbassioni

    Pages 1-17

19. Pure Point Diffractive Substitution Delone Sets Have the Meyer Property

    • Jeong-Yup Lee, Boris Solomyak

    Pages 1-20

20. Metric Combinatorics of Convex Polyhedra: Cut Loci and Nonoverlapping Unfoldings

    • Ezra Miller, Igor Pak

    Pages 1-50

While we were busy putting together the present collection of articles celebrating the twentieth birthday of our journal, Discrete & Computational Geometry, and, in a way, of the ?eld that has become known under the same name, two more years have elapsed. There is no doubt that DCG has crossed the line between childhood and adulthood. By the mid-1980s it became evident that the solution of many algorithmic qu- tions in the then newly emerging ?eld of computational geometry required classical methodsandresultsfromdiscreteandcombinatorialgeometry. Forinstance,visibility and ray shooting problems arising in computer graphics often reduce to Helly-type questions for line transversals; the complexity (hardness) of a variety of geometric algorithms depends on McMullen’s upper bound theorem on convex polytopes or on the maximum number of “halving lines” determined by 2n points in the plane, that is, the number of different ways a set of points can be cut by a straight line into two parts of the same size; proximity questions stemming from several application areas turn out to be intimately related to Erdos’ ? s classical questions on the distribution of distances determined by n points in the plane or in space. On the other hand, the algorithmic point of view has fertilized several ?elds of c- vexity and of discrete geometry which had lain fallow for some years, and has opened new research directions.

• Combinatorics
• combinatorial geometry
• complex geometry
• computational geometry
• computer graphics
• general convexity
• polyhedra
• polytopes
• real algebraic geometry
• real analytic geometry
• real geometry

Jacob Goodman, Richard Pollack and János Pach are each distinguished professors and authors in their own right, and together they are the pre-eminent founders and editors-in-chief of the journal, Discrete & Computational Geometry. Over the 20 years since the founding of this premiere journal, it has become synonymous with the field of discrete and computational geometry itself.

Policies and ethics