Binary Search Partitions for Fat Rectangles

The authors consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in R/sup 3/ such that the aspect ratio of each rectangle in S is at most /spl alpha/, for some constant a /spl alpha//spl ges/1. They present an n2/sup O(/spl radic/logn)/-time algorithm to build a binary space partition of size n2/sup O(/spl radic/logn)/ for S. They also show that if m of the n rectangles in S have aspect ratios greater than /spl alpha/, they can contact a BSP of size n/spl radic/m2/sup O(/spl radic/logn)/ for S in n/spl radic/2/sup O(/spl radic/logn)/ time. The constants of proportionality in the big-oh terms are linear in log /spl alpha/. They extend these results to cases in which the input contains non-orthogonal or intersecting objects.

Authors

• Pankaj K. Agarwal
• Edward F. Grove
• T. M. Murali 0001
• Jeffrey Scott Vitter

Keywords

• Computer science
• Computer graphics
• Hardware
• Rendering (computer graphics)
• Military computing
• Layout
• Computational geometry
• Pixel
• Costs
• Engines
• Aspect Ratio
• Proportionality Constant
• Bounding Box
• Hyperplane
• Number Of Objects
• Subtree
• Convex Objective
• Department Of Computer Science
• Input Object
• N Log N
• Beginning Of Each Round