[Géométrie algorithmique] Triangulation
Bonjour à toutes et à tous,
Je me permet de vous embêter, car j'ai une présentation a faire ce mercredi sur un papier scientifique mais je ne comprend pas le premier Lemma de celui-ci.
Le papier propose un algorithme pour calculer la triangulation de Delaunay de points imprécis (voilà le papier si vous êtes curieux : https://hal.inria.fr/inria-00595823/document).
Le contexte :
Ce que l'on appel un point imprécis c'est une zone (un disque unitaire) définissant où se situera le "vrai" point (que l'on appelle instance).
Une hypothèse de presque tous les algorithmes en géométrie est que les points d’entrée sont donnés avec précision, il est donc intéressant de se demander quelle est la valeur d’une information imprécise sur les points. L'article montre comment prétraiter un ensemble de n disques unitaires disjoints dans le plan en temps O (n log n) de sorte que, si un point par disque est spécifié avec des coordonnées précises, la triangulation de Delaunay puisse être calculée en temps linéaire.
Supposition :
On suppose dans cette démonstration que les points imprécis sont des disques unitaires disjoints.
Les notations sont les suivantes :
notations.png
Le petit Lemma que je ne comprend pas est le suivant :
problem.png
Ce que je ne comprend pas :
Je trouve que ce lemma est trop peu détailler pour moi. Il y a deux points qui restent très confus :
- D'ou sort la distance de 2.37 ?
- Comment l'auteur arrive t-il a conclure que la taille de W(q) est borné par 12 + le nombre de disques unitaire au maximum à moins de 2.37 de distances ?
Si vous avez compris, une piste, des indices, ou même une intuition, je suis tout ouïe
Merci d'avance et bonne année à tous !
Azerus
-----
Re : [Géométrie algorithmique] Triangulation
