Most scientific and engineering disciplines today have enormous opportunities for creation of knowledge from massive quantities of data available to them. But the lack of appropriate algorithms and analysis tools for processing, organizing, and querying this data deluge makes this task extremely challenging. A large portion of the data being acquired today has a geometric character, and even non-geometric data are often best analyzed by embedding them in a multi-dimensional feature space and exploiting the geometry of that space. This data is invariably full of noise, inaccuracies, outliers, is often incomplete and approximate, yet most of the existing geometric algorithms are unable to cope with any data uncertainty in relating their output to their input.
The project aims to fill this void by investigating uncertainty-aware geometric computing, with an express goal of designing algorithmic techniques and foundations that will help extract ``knowledge'' from large quantities of geometric data in the presence of various non-idealities and uncertainties. It focuses on a number of fundamental geometric problems, all dealing with uncertain data. A unified set of models will be developed for modeling uncertainty that can deal with multiple uncertainty types, and attention will be paid to handling noise/outliers in heterogeneous and dynamic data. Algorithms will be investigated for understanding how input uncertainty carries over to output uncertainty (e.g. by associating a confidence level or likelihood with each output, or computing certain statistics of the output) and how the input uncertainty impacts the quality of the output (e.g. by defining and computing the stability of the output in terms of the input uncertainty). Since exact solutions are likely to be computationally infeasible, the emphasis will be on simple, efficient approximation techniques (e.g. computing a compact, approximate distribution of geometric/topological structures such as Delaunay triangulations and their subcomplexes of uncertain data).
A key ingredient of the award is to address a variety of computational issues that arise in the presence of uncertainty using a few key problems, and to develop a core set of techniques that illuminate algorithmic design under uncertainty not only on these key problems but that can also be transferred to other geometric problems, as needed. This research touches upon many topics in theoretical computer science and applied mathematics including discrete and computational geometry, discrete and continuous optimization, estimation theory, and machine learning. This study will strengthen connections of computational geometry with a variety of disciplines, including machine learning, probabilistic databases, statistics, and GIS. Since so many problems require geometric data analysis, the project has the potential of enhancing the capability of various government, commercial, and civic units to make informed decisions that impact the society at large.
