AF:Medium:Collaborative Research: Uncertainty Aware Geometric Computing

当今，大多数科学和工程学科都有从大量可用数据中创造知识的巨大机会。 但是，由于缺乏适当的算法和分析工具来处理、组织和查询这些海量数据，这项任务极具挑战性。 今天采集的大部分数据都具有几何特征，即使是非几何数据也通常通过将其嵌入多维特征空间并利用该空间的几何形状来进行最佳分析。 这些数据总是充满了噪音，不准确，离群值，通常是不完整和近似的，然而大多数现有的几何算法无法科普任何数据的不确定性，将其输出与输入相关联。该项目旨在通过研究不确定性感知的几何计算来填补这一空白，明确的目标是设计算法技术和基础，这将有助于在存在各种非几何数据的情况下从大量几何数据中提取“知识”。理想和不确定性。 它集中在一些基本的几何问题，所有处理不确定的数据。 将开发一套统一的模型，用于对可处理多种不确定性类型的不确定性进行建模，并将注意处理异质和动态数据中的噪声/离群值。 将研究算法，以了解输入不确定性如何转移到输出不确定性（例如，通过将置信度或可能性与每个输出相关联，或计算输出的某些统计数据）以及输入不确定性如何影响输出的质量（例如，通过定义和计算输出的稳定性输入不确定性）。 由于精确解很可能在计算上是不可行的，所以重点将放在简单有效的近似技术上（例如，计算几何/拓扑结构的紧凑近似分布，例如Delaunay三角剖分及其不确定数据的子复合体）。该奖项的一个关键要素是使用几个关键问题解决存在不确定性时出现的各种计算问题，并开发一套核心技术，不仅在这些关键问题上，而且还可以根据需要转移到其他几何问题上，来阐明不确定性下的算法设计。 这项研究涉及理论计算机科学和应用数学的许多主题，包括离散和计算几何，离散和连续优化，估计理论和机器学习。 这项研究将加强计算几何与各种学科的联系，包括机器学习，概率数据库，统计学和GIS。 由于如此多的问题需要几何数据分析，该项目有可能提高各种政府，商业和公民单位做出影响整个社会的明智决策的能力。

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.