Cylindrical static and kinetic binary space partitions


Journal Article

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(n2), 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 R3. We present a randomized algorithm that constructs a BSP of expected size O(n2) in O(n2 log2 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)log2 n) time, where k is the number of intersection points between the edges of the projections of the triangles onto the xy-plane.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Guibas, LJ; Murali, TM; Vitter, JS

Published Date

  • January 1, 1997

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 39 - 48

Digital Object Identifier (DOI)

  • 10.1145/262839.262858

Citation Source

  • Scopus