AF: Small: Geometric Data Processing and Analysis via Light-weight Structures

在当前的信息时代，科学和工程中经常会产生大量复杂的数据。几何和拓扑数据分析是组织、分析和利用产生的海量数据的主要组成部分。随着数据变得更加复杂和高维，从数据计算和维护局部结构在计算上可能非常困难。因此，确定和使用能够有效计算、维护和/或操纵的轻质结构变得至关重要；同时也具有足够的信息量。这个项目将专注于两个这样的轻量级结构：里布图和高斯权重图拉普拉斯。它们都已被广泛用于各种数据分析应用。然而，有许多关于它们的理论和算法问题需要解决，以更好地理解它们的行为、它们的潜力，以及进一步它们的实际应用。本项目旨在解决这些问题，为它们的实际应用开发坚实的理论基础和高效的算法，并基于这两个对象研究新的几何处理应用。数据分析是计算科学中的一个基本问题，普遍存在于科学和工程的广泛应用领域。该项目的智力价值不仅在于开发新的计算几何算法和技术，而且还在于将结果和见解转化为实际应用。该项目的成果，特别是算法和软件，将传播给大型科学界，以便有可能在科学和工程工作中产生更广泛的影响。

In the current era of information, large amounts of complex data are routinely generated across science and engineering. Geometric and topological data analysis is a major component involved in organizing, analyzing, as well as utilizing the huge amount of data generated. As data becomes more complex and high dimensional, it can be computationally formidable to compute and maintain even local structures from data. Hence it has become crucial to identify and use light-weight structures that can be efficiently computed, maintained and/or manipulated; while at the same time are also sufficiently informative. This project will focus on two such light-weight structures: the Reeb graph and the Gaussian-weighted graph Laplacian. Both of them have already been extensively used for various data analysis applications. Nevertheless, there are many theoretical and algorithmic questions about them that need to be addressed to better understand their behavior, their potential, as well as to further their practical usage. This project aims to address these issues, develop a solid theoretical foundation as well as efficient algorithms for their practical usage, and investigate novel geometric processing applications based on these two objects. Data analysis is a fundamental problem in computational science, ubiquitous in a broad range of application fields in science and engineering. The intellectual value of this project lies not only in developing novel computational geometry algorithms and techniques, but also in transferring the results and insights to practical applications. Results from this project, especially algorithms and software, will be disseminated to a large scientific community so as to potentially produce a broader impact in scientific and engineering endeavors.