Arrangements in Computational Geometry: Past, Present, and Future
Friday, April 18, 2003
Host: Richard Cole, email@example.com, 212-998-3119
We review the progress, during the past 20 years, in the study of arrangements of curves in the plane and of surfaces in higher dimensions. (Informally, such an arrangement is the subdivision of space induced by ``drawing'' the given surfaces.) Arrangements of this kind are a central construct in computational geometry, and arise in many applications, such as motion planning in robotics, ray shooting and visibility in three dimensions, Voronoi diagrams, geometric optimization, union of geometric objects, and more. In these applications, one is interested not in the full arrangement, but in various portions, such as the lower or upper envelope of the surfaces, a single cell of the arrangement, a `zone' traced by another surface, etc.
The extensive study of arrangements has led to many nearly tight bounds on the complexity of lower envelopes, single cells, zones, and other substructures in such arrangements, and to the design of efficient algorithms (near optimal in the worst case) for constructing and manipulating these structures, and for a myriad of applications in the various areas mentioned above. We will present several highlights of the theory and of its applications, focussing on the more recent developments and on the challenges that still lie ahead.