Studies of Geometric Arrangements and their Algorithmic Applications

New York University, New York NY

Investigators

Abstract

Computational geometry covers a wide range of applications, such as motion planning and computer graphics, and its contribution to their solution involves the use of sophisticated techniques drawn from many branches of mathematics and computer science. The investigators extensively study many basic and applied problems in the area, including motion planning, Voronoi diagrams, combinatorial and algebraic analysis of arrangements of curves and algebraic surfaces, graph drawing, randomized algorithms, and geometric optimization. A major portion of this research involves the study of arrangements of curves and surfaces. The significant progress made by the PI's on these problems during the past 15 years has opened up many new challenging research directions, including: Combinatorial and algorithmic problems related to substructures (lower envelopes, single cells, zones, levels, vertical decompositions) in arrangements of surfaces in higher dimensions. Related algorithms in real algebraic geometry for computing connected components, stratifications, the dimension and other topological parameters of real semi-algebraic sets. Graph drawing and other algorithmic, combinatorial, and topological problems involving planar arrangements of segments or curves. Applications of these results to numerous areas, including motion planning in robotics, rendering and modeling problems in computer graphics, generalized Voronoi diagrams and geometric optimization problems, including problems in metrology and facility location. An important feature of this research is the cross-fertilization between basic research in computational and combinatorial geometry and various application areas. Another theme is the strong connection between the combinatorial analysis of arrangements and the design of efficient algorithms for constructing and utilizing these structures. The efficiency of the algorithms often crucially depends on the size of the structure to be computed, and most of the work is devoted to bounding this quantity.