Math @ Duke

Publications [#235602] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Erickson, J; Guibas, LJ, Kinetic binary space partitions for intersecting segments and disjoint triangles,
in Ninth Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(1998),
pp. 107116
(last updated on 2018/02/24)
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 twodimensional 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 threedimensional 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 xyprojection 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) DavenportSchinzel sequence for some constant s.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

