Filtering Relocations on a Delaunay Triangulation

Simple item page
dc.contributor.authorManhaes de Castro, Pedro Machadoen_US
dc.contributor.authorTournois, Janeen_US
dc.contributor.authorAlliez, Pierreen_US
dc.contributor.authorDevillers, Olivieren_US
dc.date.accessioned2015-02-23T15:43:32Z
dc.date.available2015-02-23T15:43:32Z
dc.date.issued2009en_US
dc.description.abstractUpdating 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.en_US
dc.description.number5en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume28en_US
dc.identifier.doi10.1111/j.1467-8659.2009.01523.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages1465-1474en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2009.01523.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltden_US
dc.titleFiltering Relocations on a Delaunay Triangulationen_US
Files
Collections
28-Issue 5
SGP09: Eurographics Symposium on Geometry Processing