McGill University - School of Computer Science

Algorithms Seminar 2003

Everybody is welcome!

DATE: Wednesday, January 22nd
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: Binary space partitions for orthogonal fat rectangles
SPEAKER: Csaba David Toth, University of California, Department of Computer Science.

The binary space partition (BSP) is a recursive cutting scheme for a set of n disjoint polygonal scenes in the Euclidean space. We split the space along a plane into two parts and then we partition recursively the two parts until the interior of every space fragment is disjoint from the polygonal scenes. The size of a BSP is the number of splits made. Since the efficiency of algorithms using this data structure vitally depends on the size of the BSP, we want to find small BSPs.

Paterson and Yao proved that the size of the smallest BSP for n rectangles is Theta(n^2) in the worst case; and Theta(n^{3/2}) if all rectangles are orthogonal. Later, Agarwal et al. showed that for n orthogonal fat rectangles, there is a BSP of size n 2^{(log n)^{1/2}}. In this talk, I show that one can generate a BSP of size O(n log^8 n) for n orthogonal fat rectangles, using the new technique of overlaying BSPs.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at , or .
Web Address: