## 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 log^{2} 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 log^{2} n+k′), construction time O(n log^{3} n+k′log n), and update time O(log^{2} 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 language | English (US) |
---|---|

Pages | 107-116 |

Number of pages | 10 |

State | Published - Dec 1 1998 |

Externally published | Yes |

Event | Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA Duration: Jan 25 1998 → Jan 27 1998 |

### Other

Other | Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms |
---|---|

City | San Francisco, CA, USA |

Period | 1/25/98 → 1/27/98 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)