Kinetic stable Delaunay graphs

Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas, Haim Kaplan, Vladlen Koltun, Natan Rubin, Micha Sharir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations


The best known upper bound on the number of topological changes in the Delaunay triangulation of a set of moving points in ℝ2 is (nearly) cubic, even if each point is moving with a fixed velocity. We introduce the notion of a stable Delaunay graph (SDG in short), a dynamic subgraph of the Delaunay triangulation, that is less volatile in the sense that it undergoes fewer topological changes and yet retains many useful properties of the full Delaunay triangulation. SDG is defined in terms of a parameter α > 0, and consists of Delaunay edges pq for which the (equal) angles at which p and q see the corresponding Voronoi edge epq are at least α. We prove several interesting properties of SDG and describe two kinetic data structures for maintaining it. Both structures use O*(n) storage. They process O* (n2) events during the motion, each in O*(1) time, provided that the points of P move along algebraic trajectories of bounded degree; the O*(·) notation hides multiplicative factors that are polynomial in 1/α and polylogarithmic in n. The first structure is simpler but the dependency on 1/α in its performance is higher.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
Number of pages10
StatePublished - 2010
Externally publishedYes
Event26th Annual Symposium on Computational Geometry, SoCG 2010 - Snowbird, UT, United States
Duration: Jun 13 2010Jun 16 2010

Publication series

NameProceedings of the Annual Symposium on Computational Geometry


Conference26th Annual Symposium on Computational Geometry, SoCG 2010
Country/TerritoryUnited States
CitySnowbird, UT

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


  • Delaunay triangulation
  • Kinetic data structures
  • Voronoi diagram


Dive into the research topics of 'Kinetic stable Delaunay graphs'. Together they form a unique fingerprint.

Cite this