Regular triangulations of dynamic sets of points

The Delaunay triangulations of a set of points are a class of triangulations which play an important role in a variety of different disciplines of science. Regular triangulations are a generalization of Delaunay triangulations that maintain both their relationship with convex hulls and with Voronoi...

Full description

Saved in:
Bibliographic Details
Published in:Computer aided geometric design 2002-02, Vol.19 (2), p.127-149
Main Authors: Vigo, Marc, Pla, Núria, Cotrina, Josep
Format: Article
Language:English
Subjects:
Applied sciences
Computer aided design
Computer science
control theory
systems
Convex hulls
Delaunay and regular triangulations
Exact sciences and technology
Incremental algorithms
Software
Voronoi diagrams
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Delaunay triangulations of a set of points are a class of triangulations which play an important role in a variety of different disciplines of science. Regular triangulations are a generalization of Delaunay triangulations that maintain both their relationship with convex hulls and with Voronoi diagrams. In regular triangulations, a real value, its weight, is assigned to each point. In this paper a simple data structure is presented that allows regular triangulations of sets of points to be dynamically updated, that is, new points can be incrementally inserted in the set and old points can be deleted from it. The algorithms we propose for insertion and deletion are based on a geometric interpretation of the history data structure in one more dimension and use lifted flips as the unique topological operation. This results in rather simple and efficient algorithms. The algorithms have been implemented and experimental results are given.
ISSN:0167-8396
1879-2332
DOI:10.1016/S0167-8396(01)00082-6