AF: Small: Approximation, Covering and Clustering in Computational Geometry

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Computational geometry is the branch of theoretical computer science devoted to the design, analysis, and implementation of geometric algorithms and data structures. Computational geometry has deep roots in reality: Geometric problems arise naturally in any computational field that simulates or interacts with the physical world---computer graphics, robotics, geographic information systems, computer aided-design, and molecular modeling, to name a few---as well as in more abstract domains such as combinatorial geometry and algebraic topology. This research focuses on fundamental problems in computational geometry. These problems include set-cover, hitting set, independent set, and other related problems. These problems have numerous applications from wireless networking to optimization. The main theme of this research is to combine ``classical'' Computational Geometry techniques (like cuttings, epsilon-nets, etc) together with techniques used in Operation Research (Linear Programming, rounding techniques, etc). This research aims to greatly improve our understanding of the structure of these fundamental problems. The research may lead to improved approximation algorithms for these problems. The algorithms and insights obtained from the technical work will benefit computer science and related disciplines where geometric algorithms are widely used. This research has potential to broaden the scope of Computational Geometry by introducing new techniques into the field. A book partially based on the research in this award will be published in the near future. This will make the developed techniques available to wide audience consisting of students and researchers from several disciplines include engineering, mathematics, and the natural and social sciences.