Skip to Main content Skip to Navigation
Journal articles

Vertex Removal in Two Dimensional Delaunay Triangulation: Speed-up by Low Degrees Optimization

Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : The theoretical complexity of vertex removal in a Delaunay triangulation is often given in terms of the degree d of the removed point, with usual results O(d), O(d log d), or O(d²). In fact, the asymptotic complexity is of poor interest since d is usually quite small. In this paper we carefully design code for small degrees 3≤ d≤ 7, it improves the global behavior of the removal for random points by more than 45%.
Document type :
Journal articles
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download


https://hal.inria.fr/inria-00560379
Contributor : Olivier Devillers <>
Submitted on : Friday, January 28, 2011 - 11:15:11 AM
Last modification on : Saturday, January 27, 2018 - 1:31:40 AM
Document(s) archivé(s) le : Tuesday, November 6, 2012 - 12:30:59 PM

Files

paper.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Olivier Devillers. Vertex Removal in Two Dimensional Delaunay Triangulation: Speed-up by Low Degrees Optimization. Computational Geometry, Elsevier, 2011, 44, pp.169-177. ⟨10.1016/j.comgeo.2010.10.001⟩. ⟨inria-00560379⟩

Share

Metrics

Record views

420

Files downloads

1000