Kinetic binary space partitions for intersecting segments and disjoint triangles

Pankaj K. Agarwal, Jeff Erickson, Leonidas J. Guibas

Research output: Contribution to conferencePaperpeer-review

Abstract

We describe randomized algorithms for efficiently maintaining a binary space partition of continuously moving, possibly intersecting, line segments in the plane, and of continuously moving but disjoint triangles in space. Our two-dimensional BSP has depth O(log n) and size O(n log n+k) and can be constructed in expected O(n log2 n+k log n) time, where k is the number of intersecting pairs. We can detect combinatorial changes to our BSP caused by the motion of the segments, and we can update our BSP in expected O(log n) time per change. Our three-dimensional BSP has depth O(log n), size O(n log2 n+k′), construction time O(n log3 n+k′log n), and update time O(log2 n) (all expected), where k′ is the number of intersections between pairs of edges in the xy-projection of the triangles. Under reasonable assumptions about the motion of the segments or triangles, the expected number of number of combinatorial changes to either BSP is O(mnλs(n)), where m is the number of moving objects and λs(n) is the maximum length of an (n, s) Davenport-Schinzel sequence for some constant s.

Original languageEnglish (US)
Pages107-116
Number of pages10
StatePublished - Dec 1 1998
Externally publishedYes
EventProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 25 1998Jan 27 1998

Other

OtherProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA
Period1/25/981/27/98

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Kinetic binary space partitions for intersecting segments and disjoint triangles'. Together they form a unique fingerprint.

Cite this