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, whose interiors remain disjoint throughout the motion. Under reasonable assumptions on the motion, we show that the total number of times this BSP changes is O(n2), and that we can update the BSP in O(log n) expected time per change. Throughout the motion, the expected size of the BSP is O(n log n). We also consider the problem of constructing a BSP for n static triangles with pairwise-disjoint interiors in ℝ3. We present a randomized algorithm that constructs a BSP of size O(n2) in O(n2log2 n) expected time. We also describe a deterministic algorithm that constructs a BSP of size O((n + k) log2 n) and height O(log n) in O((n + k) log3 n) time, where k is the number of intersection points between the edges of the projections of the triangles onto the xy-plane. This is the first known algorithm that constructs a BSP of O(log n) height for disjoint triangles in ℝ3. © 2000 Elsevier Science B.V. All rights reserved.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 2000

Published In

Volume / Issue

  • 16 / 2

Start / End Page

  • 103 - 127

International Standard Serial Number (ISSN)

  • 0925-7721

Digital Object Identifier (DOI)

  • 10.1016/S0925-7721(00)00005-5

Citation Source

  • Scopus