This volume is a collection of refereed expository and research articles in discrete and computational geometry written by leaders in the field. Articles are based on invited talks presented at the AMS-IMS-SIAM Summer Research Conference, "Discrete and Computational Geometry: Ten Years Later", held in 1996 at Mt. Holyoke College (So. Hadley, MA). Topics addressed range from tilings, polyhedra, and arrangements to computational topology and visibility problems. Included are papers on the interaction between real algebraic geometry and discrete and computational geometry, as well as on linear programming and geometric discrepancy theory.

Readership

Graduate students and research mathematicians working in discrete and computational geometry; applied workers using geometric methods and results, such as computer graphics and design.

Table of Contents

• P. K. Agarwal and J. Erickson -- Geometric range searching and its relatives
• N. Amenta and G. M. Ziegler -- Deformed products and maximal shadows of polytopes
• L. J. Billera, C. S. Chan, and N. Liu -- Flag complexes, labelled rooted trees, and star shellings
• B. Chazelle -- Discrepancy bounds for geometric set systems with square incidence matrices
• T. K. Dey, H. Edelsbrunner, and S. Guha -- Computational topology
• G. Fejes Tóth -- Recent progress on packing and covering
• B. Grünbaum -- Acoptic polyhedra
• F. Holt and V. Klee -- A proof of the strict monotone 4-step conjecture
• I. Itenberg and M.-F. Roy -- Interactions between real algebraic geometry and discrete and computational geometry
• J. O'Rourke -- Open problems in the combinatorics of visibility and illumination
• J. Pach and J. Solymosi -- Halving lines and perfect cross-matchings
• J. Pach, T. Thiele, and G. Tóth -- Three-dimensional grid drawings of graphs
• M. Pocchiola and G. Vegter -- On polygonal covers
• J. Richter-Gebert -- The universality theorems for oriented matroids and polytopes
• M. Senechal -- Periodic and aperiodic tilings of \(E^n\)
• M. I. Shamos -- The early years of computational geometry-A personal memoir
• M. Sharir -- Arrangements of surfaces in higher dimensions
• J. Spencer -- Geometric discrepancy theory
• H. Tverberg -- Proof of Reay's conjecture on certain positive-dimensional intersections
• R. Wenger -- Progress in geometric transversal theory
• G. M. Ziegler -- Recent progress on polytopes
• Application challenges to computational geometry (CG impact task force report)