43 KAM Mathematical Colloquium

Prof. MICHA SHARIR

Tel Aviv University

RECENT DEVELOPMENTS IN THE THEORY OF ARRANGEMENTS OF SURFACES


May 22, 2001 Lecture Room S4, Charles University, Malostranske nam. 25, Praha 1 14:00 PM

Abstract

We review recent progress in the study of arrangements of surfaces in higher dimensions. This progress involves new and nearly tight bounds on the complexity of lower envelopes, single cells, zones, and other substructures in such arrangements, and the design of efficient algorithms (near optimal in the worst case) for constructing and manipulating these structures. We also discuss applications of the new results to motion planning, Voronoi diagrams, union of geometric objects, visibility, and geometric optimization.