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
Conference papers

Fast Delaunay Triangulation for Converging Point Relocation Sequences

Pedro Machado Manhães de Castro 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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. Experiments show 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 several times faster than rebuilding.
Document type :
Conference papers
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

Contributor : Pedro Machado Manhaes de Castro Connect in order to contact the contributor
Submitted on : Thursday, September 3, 2009 - 6:16:00 PM
Last modification on : Monday, December 14, 2020 - 4:46:30 PM
Long-term archiving on: : Tuesday, June 15, 2010 - 11:10:58 PM


Files produced by the author(s)


  • HAL Id : inria-00413351, version 1



Pedro Machado Manhães de Castro, Olivier Devillers. Fast Delaunay Triangulation for Converging Point Relocation Sequences. European Workshop on Computational Geometry, 2009, Bruxelles, Belgium. ⟨inria-00413351⟩



Record views


Files downloads