AF: Small: Topological Approximation Techniques in Computational Geometry

University Of Texas At Dallas, Richardson TX

Investigators

Abstract

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.