Computer Science Department

Computer Science Colloquium

Arrangements in Computational Geometry: Past, Present, and Future

Micha Sharir
New York University

Friday, April 18, 2003
11:30 a.m.
Room 1302 WWH
251 Mercer Street
New York, NY 10012-1185

Host: Richard Cole,, 212-998-3119
Colloquium Information:


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.