HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 metadata

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/inria-00325816
Contributor : Pedro Machado Manhaes de Castro Connect in order to contact the contributor
Submitted on : Tuesday, September 30, 2008 - 2:12:02 PM
Last modification on : Friday, February 4, 2022 - 3:24:15 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

175

Files downloads

362