Stretch Factor of Long Paths in a planar Poisson-Delaunay Triangulation

Nicolas Chenavier 1 Olivier Devillers 2
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Résumé : Soit $X:=X_n\cup\{(0,0),(1,0)\}$, où $X_n$ est un processus ponctuel de Poisson planaire d'intensité $n$. Nous montrons que la longueur du plus court chemin entre $(0,0)$ et $(1,0)$ dans la triangulation de Delaunay de $X$ est dans l'intervalle $[1+2.47\cdot 10^{-11}, 1.182]$ quand $n$ tends vers l'infini. Les résultats expérimentaux indiquent que la valeur correcte est 1.04. Nous montrons aussi que l'espérance du nombre d'arêtes de Delaunay coupées par le segment $[(0,0),(1,0)]$ est $\frac{64}{3\pi^2}\sqrt{n}+O(1)\simeq2.16\sqrt{n}$. Le code pour les simulations et la feuille de calcul Maple sont disponibles avce ce rapport de recherche.
Type de document :
Rapport
[Research Report] RR-8935, Inria. 2016, pp.34
Liste complète des métadonnées

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


https://hal.inria.fr/hal-01346203
Contributeur : <>
Soumis le : lundi 18 juillet 2016 - 14:44:57
Dernière modification le : mardi 13 décembre 2016 - 15:43:39

Identifiants

  • HAL Id : hal-01346203, version 1
  • Mot de passe : ews89n
  • ARXIV : 1607.05770

Citation

Nicolas Chenavier, Olivier Devillers. Stretch Factor of Long Paths in a planar Poisson-Delaunay Triangulation. [Research Report] RR-8935, Inria. 2016, pp.34. 〈hal-01346203〉

Partager

Métriques

Consultations de la notice

402

Téléchargements de fichiers

102