A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs

Gary Miller 1 Donald Sheehy 2 Ameya Velingker 1
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We present a new algorithm that produces a well-spaced superset of points conforming to a given input set in any dimension with guaranteed optimal output size. We also provide an approximate Delaunay graph on the output points. Our algorithm runs in expected time $O(2^{O(d)}(n\log n + m))$, where $n$ is the input size, $m$ is the output point set size, and $d$ is the ambient dimension. The constants only depend on the desired element quality bounds. To gain this new efficiency, the algorithm approximately maintains the Voronoi diagram of the current set of points by storing a superset of the Delaunay neighbors of each point. By retaining quality of the Voronoi diagram and avoiding the storage of the full Voronoi diagram, a simple exponential dependence on $d$ is obtained in the running time. Thus, if one only wants the approximate neighbors structure of a refined Delaunay mesh conforming to a set of input points, the algorithm will return a size $2^{O(d)}m$ graph in $2^{O(d)}(n\log n + m)$ expected time. If $m$ is superlinear in $n$, then we can produce a hierarchically well-spaced superset of size $2^{O(d)}n$ in $2^{O(d)}n\log n$ expected time.
Type de document :
Communication dans un congrès
ACM Symposium on Computational Geometry, 2013, Rio de Janeiro, Brazil. pp.289--298, 2013
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00924494
Contributeur : Donald Sheehy <>
Soumis le : lundi 6 janvier 2014 - 20:17:26
Dernière modification le : samedi 27 janvier 2018 - 01:31:01
Document(s) archivé(s) le : jeudi 10 avril 2014 - 17:45:23

Fichier

miller13fast.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00924494, version 1

Collections

Citation

Gary Miller, Donald Sheehy, Ameya Velingker. A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs. ACM Symposium on Computational Geometry, 2013, Rio de Janeiro, Brazil. pp.289--298, 2013. 〈hal-00924494〉

Partager

Métriques

Consultations de la notice

216

Téléchargements de fichiers

347