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.
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 parsimonious representation, yielding an approximate solution to the original optimization problem by using inexpensive calculations. Core-sets are exciting because of their applications in the development of powerful, practical and general algorithmic techniques that are applicable to a large class of problems. During this project, we published more than 15 peer reviewed publications in journals and conferences that either extend the class of problems that core-sets apply to or are applications of core-sets to various areas like Geographic Information Systems, Graphics, Optimization, Experimental Algorithmics, RFID applications and Databases. Some of the major advances that we made were by designing and implementing : efficient core-set algorithms for the widely used Support Vector Machine problem, axis aligned minimum volume ellipsoid problem, weighted 1-center and k-clustering problems. In all cases, core-set based methods turned out to be better than earlier known methods in at least certain aspects. fast algorithms for the nearest neighbor search problem and geometric minimum spanning tree problems for lower dimensional spaces. Both these problems are widely used in many disciplines of the sciences, especially for clustering large data sets when the metric is Euclidian. algorithms for computing centers on road networks, which hopefully would lead to lower energy usage and pollution in the near future. The research also helped train four graduate students. Details on student training by the PI can be found on this web page : www.compgeom.com/~piyush/students.html Publications related to this project can be found at the following webpage: www.compgeom.com/~piyush/publicat.html More details on the PI can be found at: http://piyush.compgeom.com
