Speaker: Don Sheehy
Title: Finding the Center
Abstract:
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.