Department of Mathematics,
University of California San Diego
****************************
Math 269 - Combinatorics
Csaba D. Toth
UC Santa Barbara
Binary space partitions for orthogonal fat rectangles
Abstract:
The binary space partition (BSP) is a recursive cutting scheme for aset of n disjoint polygonal scenes in the Euclidean space. We split thespace along a plane into two parts and then we partition recursivelyboth parts until the interior of every space fragment is disjointfrom the polygonal scenes. The size of a BSP is the number of splitsmade. The efficiency of applications (in computer graphics andcomputational geometry) vitally depends on the size of the BSPs.Paterson and Yao proved that the size of the smallest BSP for nrectangles is $Theta(n^2)$ in the worst case; and $Theta(n^{3/2})$ if allrectangles are orthogonal. Later, Agarwal et al. showed that for northogonal fat rectangles there is a BSP of size n $2^{(log n)^{1/2}}$.(A rectangle is fat if its aspect ratio is bounded by a constant.) Inthis talk, I show that one can generate a BSP of size $O(n log^8 n)$ forn orthogonal fat rectangles, improving the bound of Agarwal et al.,using the new technique of overlays of BSP
Host: J. Solymosi
December 10, 2002
3:00 PM
AP&M 7321
****************************