Cylindrical Static and Kinetic Binary Space Partitions

P. K. Agarwal, L. J. Guibas, T. M. Murali, and J. S. Vitter. ``Cylindrical Static and Kinetic Binary Space Partitions,'' Proceedings of the 13th Annual Symposium on Computational Geometry (SoCG'97), Nice, France, June 1997, 39-48.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

We describe the first known algorithm for efficiently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane. Under reasonable assumptions on the motion, we show that the total number of times the BSP changes is O(n²), and that we can update the BSP in $O(\log n)$ expected time per change. We also consider the problem of constructing a BSP for n triangles in three-dimensional Euclidean space. We present a randomized algorithm that constructs a BSP of expected size O(n²) in $O(n^2 \log^2 n)$expected time. We also describe a deterministic algorithm that constructs a BSP of size  ${O((n + k) \log n)}$ and height $O(\log n)$in  ${O((n + k) \log^2 n)}$ time, where k is the number of intersection points between the edges of the projections of the triangles onto the xy-plane.