CAREER: Core-Sets for Geometric Optimization and their Applications.

Florida State University, Tallahassee FL

Investigators

Abstract

In a remarkably short time since their discovery, core-sets have emerged as a powerful tool for the study of geometric optimization problems. The main idea behind the technique is to compute a small subset of the input, called the Core-Set, that `approximates' the input and allows the optimization problem to be solved on this concise representation. Core-sets are exciting because of their prospect in the development of powerful, practical and general methods that are applicable to a large class of problems from various applications including automotive and aircraft industries, space exploration, civil surveyors, the movie, computer gaming and medical industries, and developers of security and geographic information systems. This NSF Career proposal focuses on the design and implementation of efficient methods for geometric optimization problems and their applications to real-world problems using the paradigm of core-sets. As part of this proposal, application of core-sets to problems like curve and surface reconstruction from massive unorganized point clouds will also be explored. A key characteristic of the proposal is that it will help advance the knowledge across disciplines like computational geometry, convex optimization and machine learning. The use of core-sets will result in the design of algorithms that will be easier to code and will be faster and more robust. Furthermore, the PI plans to continue incorporating his research results in: (1) course development, (2) mentoring of graduate and undergraduate students by maintaining a careful balance between theory, applications, algorithms and computational projects, (3) development and maintenance of software solutions related to core-sets and their applications.