McGill University - School of Computer Science

Algorithms Seminar 2004

Everybody is welcome!

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.


Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at cs.mcgill.ca. 
Web Address: www.cs.mcgill.ca/~beezer/Seminars/seminar99.html