Cylindrical Static and Kinetic Binary Space Partitions

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