DATE: | Wednesday, March 3rd 2004. |
TIME: | 4:30 PM - 5:30 PM |
PLACE: | McConnell 320 |
TITLE: | Convex Hull Onions |
SPEAKER: | Ketan Dalal, McGill University. |
Start with a set of points in the plane. Imagine removing all the points that are on the convex hull of that set. Then continue by removing the convex hull of the points that remain. This process creates a structure known as an ``onion'' where each hull is one `layer' or `peel'.
In this talk, I will show that if the points were initially placed
independently and uniformly in a disk, then the expected number of
layers is $\Theta \left( n^{\frac{2}{3}} \right)$. Surprisingly, this
bound holds more generally for any fixed, bounded shape with a
non-empty interior (not just convex shapes). The proof combines simple
ideas from probability and geometry and no special background is
required.