Geometric Arrangements and their Algorithmic Applications

New York University, New York NY

Investigators

Abstract

Computational geometry is a major research area in computer science, which aims to design efficient algorithms for problems of geometric nature, which arise in many applications. In this research, the investigators continue their long-term study of basic and applied problems in computational geometry, including motion planning problems in robotics, visibility problems in computer graphics, efficient algorithms for linear programming and other geometric optimization problems. These studies cultivate and expose the rich cross-fertilization between basic research in computational and combinatorial geometry and the various application areas, where problems in one area motivate the study of new basic problems whose solution in turn finds applications in many others. There is a strong connection between the combinatorial, algebraic, and topological analysis of arrangements of geometric objects and the design of corresponding efficient algorithms: often the algorithmic complexity (efficiency) of such an algorithm crucially depends on the size or the degree of freedom (combinatorial or algebraic complexity, resp.) of the arrangement. A major portion of this research is devoted to the study of arrangements of curves and surfaces. Specifically, it studies (1) Combinatorial, topological and algorithmic problems related to substructures (lower envelopes, single cells, zones, levels, vertical decompositions, etc.) in arrangements of surfaces in higher dimensions; (2) Related algorithms in real algebraic geometry for computing connected components, stratifications and the dimension of real semi-algebraic sets. (3) Applications of these results to motion planning in robotics, to various visibility and intersection problems in computer graphics, to generalized Voronoi diagrams in higher dimensions, and to many geometric problems at large; and (4) Combinatorial, topological, and algorithmic problems involving planar arrangements of segments or curves, including graph drawings. This research is expected to have an impact on the interaction between mathematics and computer science in geometry, via the dissemination of its results in major conferences and workshops, the journals that they have been editing, the monographs and surveys that the investigators have been writing, and the numerous graduate students that they have been supervising.