Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision
(CS 528)

Arrangements in Computational Geometry: Past, Present, and Future

Micha Sharir,
Tel Aviv University and MSRI
Monday, Dec. 1, 2003, 4:15PM
TCSeq 200
http://graphics.stanford.edu/ba-colloquium/

Abstract

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. Micha Sharir is a Nizri Professor of Computational Geometry and Robotics in the School of Computer Science at Tel Aviv University, and a Research Professor at the Courant Institute (NYU). He has published the monograph Davenport-Schinzel Sequences and Their Geometric Applications (with P.K. Agarwal, Cambridge University Press, 1995) and about 230 research papers. He serves on the editorial boards of several technical journals, is an ACM Fellow, and is a recipient of the Max-Planck Research Prize (jointly with E. Welzl, 1992), a Doctor Honoris Causa degree from the University of Utrecht (1996), the Feher Prize in Computer Science (1999), and the Landau Prize for Research and Sciences (2002). -->

Contact: bac-coordinators@cs.stanford.edu

Back to the Colloquium Page