Twentieth Anniversary Volume: Discrete & Computational Geometry

Herausgegeben:Goodman, Jacob E.; Pach, János; Pollack, Richard

• Broschiertes Buch

Produktbeschreibung

This heavily-illustrated book contains twenty-eight major articles that present a comprehensive picture of the current state of discrete and computational geometry. Many of the articles solve long-outstanding problems in the field.

---

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.

Produktdetails

• Verlag: Springer / Springer New York / Springer, Berlin
• Artikelnr. des Verlages: 12282647, 978-0-387-87362-6
• 2009
• Seitenzahl: 656
• Erscheinungstermin: 13. November 2008
• Englisch
• Abmessung: 235mm x 155mm x 36mm
• Gewicht: 991g
• ISBN-13: 9780387873626
• ISBN-10: 0387873627
• Artikelnr.: 24953041

Autorenporträt

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.

Inhaltsangabe

There Are Not Too Many Magic Configurations.- Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles.- Robust Shape Fitting via Peeling and Grating Coresets.- Siegel's Lemma and Sum-Distinct Sets.- Slicing Convex Sets and Measures by a Hyperplane.- A Centrally Symmetric Version of the Cyclic Polytope.- On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities.- Enumeration in Convex Geometries and Associated Polytopal Subdivisions of Spheres.- Isotopic Implicit Surface Meshing.- Line Transversals to Disjoint Balls.- Norm Bounds for Ehrhart Polynomial Roots.- Helly-Type Theorems for Line Transversals to Disjoint Unit Balls.- Grid Vertex-Unfolding Orthogonal Polyhedra.- Empty Convex Hexagons in Planar Point Sets.- Affinely Regular Polygons as Extremals of Area Functionals.- Improved Output-Sensitive Snap Rounding.- Generating All Vertices of a Polyhedron Is Hard.- Pure Point Diffractive Substitution Delone Sets Have the Meyer Property.- Metric Combinatorics of Convex Polyhedra: Cut Loci and Nonoverlapping Unfoldings.- Empty Simplices of Polytopes and Graded Betti Numbers.- Rigidity and the Lower Bound Theorem for Doubly Cohen-Macaulay Complexes.- Finding the Homology of Submanifolds with High Confidence from Random Samples.- Odd Crossing Number and Crossing Number Are Not the Same.- Visibility Graphs of Point Sets in the Plane.- Decomposability of Polytopes.- An Inscribing Model for Random Polytopes.- An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions.- General-Dimensional Constrained Delaunay and Constrained Regular Triangulations, I: Combinatorial Properties.

---

There Are Not Too Many Magic Configurations.- Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles.- Robust Shape Fitting via Peeling and Grating Coresets.- Siegel’s Lemma and Sum-Distinct Sets.- Slicing Convex Sets and Measures by a Hyperplane.- A Centrally Symmetric Version of the Cyclic Polytope.- On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities.- Enumeration in Convex Geometries and Associated Polytopal Subdivisions of Spheres.- Isotopic Implicit Surface Meshing.- Line Transversals to Disjoint Balls.- Norm Bounds for Ehrhart Polynomial Roots.- Helly-Type Theorems for Line Transversals to Disjoint Unit Balls.- Grid Vertex-Unfolding Orthogonal Polyhedra.- Empty Convex Hexagons in Planar Point Sets.- Affinely Regular Polygons as Extremals of Area Functionals.- Improved Output-Sensitive Snap Rounding.- Generating All Vertices of a Polyhedron Is Hard.- Pure Point Diffractive Substitution Delone Sets Have the Meyer Property.- Metric Combinatorics of Convex Polyhedra: Cut Loci and Nonoverlapping Unfoldings.- Empty Simplices of Polytopes and Graded Betti Numbers.- Rigidity and the Lower Bound Theorem for Doubly Cohen–Macaulay Complexes.- Finding the Homology of Submanifolds with High Confidence from Random Samples.- Odd Crossing Number and Crossing Number Are Not the Same.- Visibility Graphs of Point Sets in the Plane.- Decomposability of Polytopes.- An Inscribing Model for Random Polytopes.- An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions.- General-Dimensional Constrained Delaunay and Constrained Regular Triangulations, I: Combinatorial Properties.