AF: Small: Topological Approximation Techniques in Computational Geometry

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

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.