Searching for the Center

Presented at Theory Lunch, Carnegie Mellon University, October 8, 2008

Convexity is a powerful tool for extracting combinatorial information from geometric objects. In this talk, I will survey several classical convexity theorems going back to the 1920s and show how they are useful in computational geometry today. In particular, I will focus on the problem of computing center points. A center point p for a set S is a point such that any line through p divides S evenly (at worst its a 1/3-2/3 cut). The existence of a center point follows independently from both Helly's Theorem (1923) and Tverberg's Theorem (1966). By borrowing intuition from both theorems, we arrive at a new deterministic algorithm for computing approximate center points in higher dimensions.