AF: Small: Topological Approximation Techniques in Computational Geometry

在数学中，离散几何定理中的几个定理是通过优雅地证明解的存在而建立起来的，而不是说如何找到解。例如，令人难忘的火腿三明治定理（在三维空间中）说，如果你有火腿、面包和奶酪，你可以用一刀把它们切成两半（即使你把奶酪放在冰箱里）。这些定理实际上对算法很重要——人们想要在d维中计算一个超平面，它将d-数据集平均分割，以划分工作。该项目探讨了这些问题的特殊情况，这些问题可以产生构建精确或近似解的算法，这对数据分析很重要。因为具有挑战性的问题通常可以非常简单地用彩色点来表述，所以这项研究将涉及本科生、研究生，甚至高中生的暑期课程。本提案涉及为凸几何和离散几何的一些基本定理寻找更多几何和有效的证明（导致有效的算法）-例如Caratheodory和Tverberg定理的彩色版本，火腿三明治和其他划分结果。这类定理最优雅的证明通常涉及拓扑方法——使用一些不动点定理、斯伯纳引理、博苏克-乌拉姆定理或更一般的特征类论证。通过提供不依赖于拓扑结构的证明，本项目可以创建更快的分区算法。

In mathematics, several theorems in discrete geometry theorems are established by elegant proofs that a solution exists, without saying how to find one. For example, the memorably named Ham Sandwich theorem says (in three dimensions) that if you have ham, bread, and cheese, you can cut all three in half with one straight cut (even if you left the cheese in the refrigerator.) These theorems can actually be important for algorithms -- one would like to compute a hyperplane in d-dimensions that splits d-data sets evenly to divide the work. This project explores special cases of these problems that can produce algorithms that construct exact or approximate solutions, which are important for data analysis. Because the challenging problems can often be stated very simply, in terms of colored points, this research will involve undergraduates, graduate students, and even a summer course for high school students.This proposal deals with finding more geometric and effective proofs (leading to efficient algorithms) for some of the fundamental theorems of convex and discrete geometry -- such as colored versions of Caratheodory and Tverberg's theorems, ham sandwich and other partitioning results. The most elegant proofs of such theorems often involve topological methods -- using some fixed point theorem, Sperner's lemma, Borsuk-Ulam or more general characteristic class arguments. By giving proofs that do not depend on topology, this project can create faster algorithms for partitioning.