Delaunay triangulations, theory vs practice. - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

Delaunay triangulations, theory vs practice.

(1)
1
Olivier Devillers

Abstract

Thirty years ago, at the early ages of computational geometry, the game of computational geometers was to design fancy algorithms with optimal theoretical complexities. The result was usually an algorithmic journal article, but not an implementation. In the same period, some people were actually cod- ing geometric algorithms, but without regard for the asymptotic complexities, and without proof of cor- rectness of the result. They were not using the algo- rithms designed by theoreticians for two reasons [14]: - these algorithms were too intricate and - they rely on the arithmetic of real numbers, which differs from the floating-point arithmetic of comput- ers. These drawbacks of old computational geometry al- gorithms have been addressed in various ways to ob- tain algorithms that reconcile robustness, practical ef- ficiency, and theoretical guarantees. The aim of this talk is to illustrate some steps of this transition from theoretical stuff to efficient algo- rithms actually used in industrial applications. I will do this using my favorite problem: the construction of the Delaunay triangulation of a set of points and the dynamic maintenance of such a triangulation under point insertions and deletions.
Fichier principal
Vignette du fichier
EuroCG12-devillers.pdf (139.17 Ko) Télécharger le fichier
Vignette du fichier
vignette.png (331.78 Ko) Télécharger le fichier
Vignette du fichier
EuroCG12-devillers-slides.pdf (3.55 Mo) Télécharger le fichier
Vignette du fichier
T2/CMakeLists.txt (996 B) Télécharger le fichier
Vignette du fichier
T2/dynamic.cpp (1.28 Ko) Télécharger le fichier
Vignette du fichier
T2/orders.cpp (6.9 Ko) Télécharger le fichier
Vignette du fichier
T2/remove.cpp (1.6 Ko) Télécharger le fichier
Vignette du fichier
T2/static.cpp (1021 B) Télécharger le fichier
Vignette du fichier
T2/swap.cpp (1.91 Ko) Télécharger le fichier
Vignette du fichier
T2/walk.cpp (1.63 Ko) Télécharger le fichier
Vignette du fichier
T3/CMakeLists.txt (944 B) Télécharger le fichier
Vignette du fichier
T3/dynamic.cpp (883 B) Télécharger le fichier
Vignette du fichier
T3/remove.cpp (1.58 Ko) Télécharger le fichier
Vignette du fichier
T3/static.cpp (1021 B) Télécharger le fichier
Vignette du fichier
T3/swap.cpp (1.56 Ko) Télécharger le fichier
Vignette du fichier
T3/walk.cpp (1.17 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Origin : Files produced by the author(s)
Origin : Files produced by the author(s)
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Loading...

Dates and versions

hal-00850561 , version 1 (28-04-2015)

Identifiers

  • HAL Id : hal-00850561 , version 1

Cite

Olivier Devillers. Delaunay triangulations, theory vs practice.. EuroCG, 28th European Workshop on Computational Geometry, 2012, Assisi, Italy. ⟨hal-00850561⟩
295 View
972 Download

Share

Gmail Facebook Twitter LinkedIn More