Printable PDF
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

****************************