A two-dimensional kinetic triangulation with near-quadratic topological changes

Published

Journal Article

A triangulation of a set S of points in the plane is a subdivision of the convex hull of S into triangles whose vertices are points of S. Given a set S of n points in ℝ2, each moving independently, we wish to maintain a triangulation of S. The triangulation needs to be updated periodically as the points in S move, so the goal is to maintain a triangulation with a small number of topological events, each being the insertion or deletion of an edge. We propose a kinetic data structure (KDS) that processes n22 O(√log n · log log n) topological events with high probability if the trajectories of input points are algebraic curves of fixed degree. Each topological event can be processed in O(log n) time. This is the first known KDS for maintaining a triangulation that processes a near-quadratic number of topological events, and almost matches the Ωn2 lower bound [1]. The number of topological events can be reduced to nk2 O(√log k · log log n) if only k of the points are moving. © Springer 2006.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Wang, Y; Yu, H

Published Date

  • January 1, 2006

Published In

Volume / Issue

  • 36 / 4

Start / End Page

  • 573 - 592

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/s00454-006-1266-7

Citation Source

  • Scopus