Skip to Main content Skip to Navigation

Delaunay Triangulations for Moving Points

Pedro Machado Manhães de Castro 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This paper considers the problem of updating efficiently a Delaunay triangulation when vertices are moving under small perturbations. Its main contribution is a set of algorithms based on the concept of vertex tolerance. Experiment shows that it is able to outperform the naive rebuilding algorithm in certain conditions. For instance, when points, in two dimensions, are relocated by Lloyd's iterations, our algorithm performs about several times faster than rebuilding.
Document type :
Complete list of metadata
Contributor : Pedro Machado Manhaes de Castro Connect in order to contact the contributor
Submitted on : Wednesday, December 3, 2008 - 3:13:28 PM
Last modification on : Monday, December 14, 2020 - 4:46:30 PM
Long-term archiving on: : Monday, June 7, 2010 - 11:42:33 PM


Files produced by the author(s)


  • HAL Id : inria-00344053, version 1



Pedro Machado Manhães de Castro, Olivier Devillers. Delaunay Triangulations for Moving Points. [Research Report] RR-6750, INRIA. 2008. ⟨inria-00344053⟩



Les métriques sont temporairement indisponibles