• Filtering Relocations on a Del...

Result: Filtering Relocations on a Delaunay Triangulation

Title:
Filtering Relocations on a Delaunay Triangulation
Authors:
Machado Manhães de Castro, Pedro, Tournois, Jane, Alliez, Pierre, Devillers, Olivier
Contributors:
Geometric computing (GEOMETRICA), Centre Inria d'Université Côte d'Azur, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre Inria de Saclay, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-07-BLAN-0319,Triangles,New challenges in triangulations(2007)
Source:
Computer Graphics Forum, 2009, ⟨10.1111/j.1467-8659.2009.01523.x⟩
Publisher Information:
CCSD; Wiley, 2009.
Publication Year:
2009
Collection:
collection:INRIA
collection:INRIA-SOPHIA
collection:INRIA-SACLAY
collection:INRIASO
collection:INRIA_TEST
collection:TESTALAIN1
collection:INRIA2
collection:UNIV-COTEDAZUR
collection:INRIA-300009
collection:ANR
Subject Terms:
ACM: I.: Computing Methodologies, I.3: COMPUTER GRAPHICS, I.3.5: Computational Geometry and Object Modeling, I.3.5.3: Geometric algorithms, languages, and systems, [INFO.INFO-CG]Computer Science [cs], Computational Geometry [cs.CG]
Original Identifier:
HAL:
Document Type:
Journal article<br />Journal articles
Language:
English
ISSN:
0167-7055
1467-8659
Relation:
info:eu-repo/semantics/altIdentifier/doi/10.1111/j.1467-8659.2009.01523.x
DOI:
10.1111/j.1467-8659.2009.01523.x
Access URL:
https://inria.hal.science/inria-00413344
https://inria.hal.science/inria-00413344v1/document
https://inria.hal.science/inria-00413344v1/file/paper.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00413344v1
Database:
HAL

Further Information

Updating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation from scratch is surprisingly a very viable option compared to relocating the vertices. This can be explained by several recent advances in efficient construction of Delaunay triangulations. However, when all points move with a small magnitude, or when only a fraction of the vertices move, rebuilding is no longer the best option. This paper considers the problem of efficiently updating a Delaunay triangulation when its vertices are moving under small perturbations. The main contribution is a set of filters based upon the concept of vertex tolerances. Experiments show that filtering relocations is faster than rebuilding the whole triangulation from scratch under certain conditions.