State of the Art: Updating Delaunay Triangulations for Moving Points

Olivier Devillers 1 Pedro Machado Manhães de Castro 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This paper considers the problem of updating efficiently a two-dimensional Delaunay triangulation when vertices are moving. We investigate the three current state-of-the-art approaches to solve this problem: --1-- the use of kinetic data structures, --2-- the possibility of moving points from their initial to final position by deletion and insertion and --3-- the use of "almost" Delaunay structure that postpone the necessary modifications. Finally, we conclude with a global overview of the above-mentioned approaches while focusing on future works.
Document type :
Reports
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/inria-00325816
Contributor : Pedro Machado Manhaes de Castro <>
Submitted on : Tuesday, September 30, 2008 - 2:12:02 PM
Last modification on : Saturday, January 27, 2018 - 1:31:35 AM
Long-term archiving on : Monday, October 8, 2012 - 1:45:27 PM

File

RR-6665.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00325816, version 1

Collections

Citation

Olivier Devillers, Pedro Machado Manhães de Castro. State of the Art: Updating Delaunay Triangulations for Moving Points. [Research Report] RR-6665, INRIA. 2008, pp.12. ⟨inria-00325816⟩

Share

Metrics

Record views

345

Files downloads

347