Variante de la décomposition de Voronoï paramétrée par une forme géometrique plane

Thomas Iwaszko (LMIA, Université de Haute Alsace, Mulhouse)

Dans le cadre d’une thèse portant sur la conception d’une structure de données nouvelle, son calcul et sa représentation par ordinateur, nous avons défini une variante de la décomposition de Voronoi [4].

Dans cet exposé nous souhaitons présenter ladite définition et le modèle de forme géométrique plane utilisé, ainsi que leurs conséquences: diverses propriétés démontrées et illustrées.

Étant donné un ensemble de sites S et une forme plane M, nos travaux définissent un ensemble de régions du plan (une région par site, tout comme Voronoï) où chacune étend la propriété du disque vide (propre à toute cellule de Voronoï) à une «propriété de forme M vide». M doit respecter certaines contraintes mais celles-ci laissent un grande liberté de construction, notamment pour des formes non convexes.

L’intérêt théorique de ces travaux est de permettre, à terme:

• la conception d’algorithmes efficaces pour résoudre des problèmes du plan qui traitent de formes et d’informations de proximité
• de disposer d’une méthode générique pour résoudre des problèmes traités indépendamment jusqu’ici: Largest Empty xxx Among a Set of Points (avec xxx: rectangle / ellipsoid / annulus [1–3] par exemple) , Piano Mover’s Problem, Polygon Placement among Obstacles

En pratique des applications telles que: détection de motifs, planification de trajectoire, etc. sont envisageables.

Travail réalisé en collaboration avec Mahmoud Melkemi et Lhassane Idoumghar.

---

La frontière d’une forme simple: un disque ouvert	Les frontières des disques composant une forme M1	Les frontières des disques composant une forme M2
Régions «à disque vide» i.e. cellules de Voronoï	Régions à instances M1 vides (instances adjacentes à S, i.e. un site de S sur leur frontière)	Régions à instances M2 vides (instances adjacentes à S, i.e. un site de S sur leur frontière)

---

1. B. Chazelle, R.L. Drysdale and D.T. Lee, Computing the largest empty rectangle. SIAM J. Comput. 15, 1 (Feb. 1986), 300-315.
2. R.A. Dwyer and W.F. Eddy, Maximal empty ellipsoids. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Jan. 1994).
3. J.M. Díaz, F. Hurtado, H. Meijer, D. Rappaport and J. Sellarès, The Largest Empty Annulus Problem, International Journal of Computational Geometry and Applications, Vol. 13 No. 4, pp. 317-325, August 2003.
4. T. Iwaszko, M. Melkemi and L. Idoumghar, Regions of Empty Overlapping Circles. Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (jccgg 2009), to appear, available at http://www.jaist.ac.jp/~uehara/JCCGG09/.

This document was translated from L^AT_EX by H^EV^EA.