Twentieth Anniversary Volume: Discrete & Computational Geometry / Edition 1

by Jacob E. Goodman, János Pach, Richard Pollack

Overview

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 field 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 field 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 fields of c- vexity and of discrete geometry which had lain fallow for some years, and has opened new research directions.

Product Details

ISBN-13:	9780387873626
Publisher:	Springer New York
Publication date:	11/13/2008
Edition description:	2009
Pages:	635
Product dimensions:	6.10(w) x 9.20(h) x 1.30(d)

About the Author

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.

Table of Contents

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.