AF: Small: Geometric Optimization via Combinatorial Geometry

New York University, New York NY

Investigators

Abstract

The goal of this project is to consider classical optimization problems, originally stated in the context of abstract graph theory and combinatorial optimization, whose hardness as well as approximation factors have been studied extensively, and investigate them in a geometric context, that is, when the input consists of geometric objects. While considerable progress has been made on the analysis of such problems in the abstract setting, their geometric variants have received much less attention. These problems include minimum coverage of a given area, stabbing a set of geometric objects, geometric packing, and obtaining largest sets of mutually intersecting geometric objects. For each of these problems, new ideas will be explored, which aim to combine tools from computational and combinatorial geometry with traditional algorithmic tools from theoretical computer science. Specifically, this work exploits techniques such as linear programming relaxation and local search, commonly used in operation research, combinatorial optimization, and algorithm theory, with tools from computational and combinatorial geometry such as geometric arrangements, Epsilon-nets, Helly-type properties, and others. This award will help to develop a new set of tools that will not only be exploited in computational and combinatorial geometry, but will extend to other (perhaps, more applied) disciplines, such as networking, computer graphics, geographic information systems, learning and others, as they often pose problems of geometric nature. In particular, each of the problems to be investigated in this project has applications to these areas, and hence their importance is not only theoretical but also practical. The project will support and train one postdoctoral researcher in Computer Science at NYU. The PI will disseminate the research to the scientific community through conference and journal publications, teaching courses, as well as presenting her works in departmental seminars, and collaboration with researchers from various disciplines.