Vertex Removal in Two Dimensional Delaunay Triangulation: Speed-up by Low Degrees Optimization - Archive ouverte HAL Access content directly
Journal Articles Computational Geometry Year : 2011

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

(1)
1
Olivier Devillers

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%.
Fichier principal
Vignette du fichier
paper.pdf (201.91 Ko) Télécharger le fichier
Vignette du fichier
vignette-inria-00560379.jpg (60.22 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Loading...

Dates and versions

inria-00560379 , version 1 (28-01-2011)

Identifiers

Cite

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

Collections

INRIA INRIA2
181 View
842 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More