| 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.