Polygonalisation -Polygonalization

16 polygonisations d'un ensemble de six points

En géométrie computationnelle , une polygonalisation d'un ensemble fini de points dans le plan euclidien est un polygone simple avec les points donnés comme sommets. Une polygonalisation peut également être appelée polygonisation , polygonalisation simple , polygone hamiltonien , cycle hamiltonien non croisé ou cycle couvrant à bord droit sans croisement .

Chaque ensemble de points qui ne se trouve pas sur une seule ligne a au moins une polygonalisation, qui peut être trouvée en temps polynomial. Pour les points en position convexe , il n'y en a qu'un, mais pour certains autres ensembles de points, il peut y en avoir un nombre exponentiel. Trouver une polygonalisation optimale sous plusieurs critères d'optimisation naturels est un problème difficile, incluant comme cas particulier le problème du voyageur de commerce . La complexité du comptage de toutes les polygonalisations reste inconnue.

Définition

Une polygonalisation est un polygone simple ayant un ensemble donné de points dans le plan euclidien comme ensemble de sommets. Un polygone peut être décrit par un ordre cyclique sur ses sommets, qui sont reliés par paires consécutives par des segments de droite, les arêtes du polygone. Un polygone, ainsi défini, est "simple" si les seuls points d'intersection de ces segments de ligne se trouvent à des extrémités communes.

Certains auteurs ne considèrent les polygonalisations que pour les points qui sont en position générale , ce qui signifie qu'il n'y en a pas trois sur une ligne. Avec cette hypothèse, l'angle entre deux segments consécutifs du polygone ne peut pas être de 180°. Cependant, lorsque des ensembles de points avec des colinéarités sont considérés, il est généralement permis que leurs polygonalisations aient des angles de 180° en certains points. Lorsque cela se produit, ces points sont toujours considérés comme des sommets, plutôt que comme étant à l'intérieur des arêtes.

Existence

Polygonalisations d'une grille 3 × 3 . Les angles de 180° visibles dans chaque polygone sont nécessaires : pour une grille de cette taille, toutes les polygonalisations ont un angle de 180°.

Steinhaus (1964) a observé que chaque ensemble de points finis sans trois dans une ligne forme les sommets d'un polygone simple. Cependant, exiger qu'aucun trois ne soit aligné est inutilement fort. Au lieu de cela, tout ce qui est requis pour l'existence d'une polygonalisation (permettant des angles de 180°) est que les points ne se trouvent pas tous sur une seule ligne. S'ils ne le font pas, alors ils ont une polygonalisation qui peut être construite en temps polynomial . Une façon de construire une polygonalisation est de choisir n'importe quel point dans l' enveloppe convexe de (pas nécessairement l'un des points donnés). Ensuite, l'ordre radial des points autour (rupture des liens par distance à partir de q) produit l'ordre cyclique d'un polygone en forme d'étoile à travers tous les points donnés, avec dans son noyau. La même idée de trier les points radialement autour d'un point central est utilisée dans certaines versions de l' algorithme de coque convexe à balayage de Graham , et peut être effectuée dans le temps. Les polygonalisations qui évitent les angles à 180° n'existent pas toujours. Par exemple, pour les grilles carrées 3 × 3 et 5 × 5 , toutes les polygonalisations utilisent des angles de 180°.${\displaystyle q}$${\displaystyle P}$${\displaystyle q}$${\displaystyle q}$${\displaystyle O(n\log n)}$

En plus des polygonalisations en étoile, chaque ensemble de points non colinéaires a une polygonalisation qui est un polygone monotone . Cela signifie que, par rapport à une ligne droite (qui peut être prise comme axe -), chaque ligne perpendiculaire à la ligne de référence coupe le polygone dans un seul intervalle, ou pas du tout. Une construction de Grünbaum (1994) commence par trier les points par leurs coordonnées et tracer une ligne passant par les deux points extrêmes. Comme les points ne sont pas tous alignés, au moins un des deux demi-plans ouverts délimités par cette droite doit être non vide. Grünbaum forme deux chaînes polygonales monotones reliant les points extrêmes par des sous-séquences triées des points : l'une pour les points de ce demi-plan ouvert non vide, et l'autre pour les points restants. Leur union est le polygone monotone désiré. Après l'étape de tri, le reste de la construction peut être effectué en temps linéaire . ${\style d'affichage x}$${\style d'affichage x}$

Il est NP-complet pour déterminer si un ensemble de points a une polygonalisation utilisant uniquement des arêtes parallèles à l'axe. Cependant, les polygonalisations avec la contrainte supplémentaire qu'elles tournent à droite à chaque sommet, si elles existent, sont déterminées de manière unique. Chaque ligne parallèle à un axe passant par un point doit passer par un nombre pair de points, et cette polygonalisation doit relier des paires alternées de points sur cette ligne. La polygonalisation peut être trouvée dans le temps en regroupant les points par des coordonnées égales et en triant chaque groupe par l'autre coordonnée. Pour tout ensemble de points, au plus une rotation peut avoir une polygonalisation de cette forme, et cette rotation peut encore se retrouver en temps polynomial. ${\displaystyle O(n\log n)}$

Optimisation

Les problèmes de recherche d'une polygonalisation optimale (pour divers critères d'optimalité) sont souvent irréalisables par calcul. Par exemple, la solution du problème du voyageur de commerce , pour les points donnés, n'a pas de croisements. Il s'agit donc toujours d'une polygonalisation, la polygonalisation de périmètre minimum . Il est NP-difficile à trouver. De même, trouver la polygonalisation simple avec une aire minimale ou maximale est connu pour être NP-difficile et a fait l'objet de quelques efforts de calcul. L'aire maximale est toujours supérieure à la moitié de l'aire de l' enveloppe convexe , ce qui donne un rapport d'approximation de 2. La complexité exacte de la polygonalisation simple à périmètre maximum, et l'existence d'un rapport d'approximation constant pour ce problème, restent inconnues. La polygonalisation qui minimise la longueur de son arête la plus longue est également NP-difficile à trouver, et difficile à approximer à un rapport d'approximation meilleur que ; aucune approximation à facteur constant n'est connue. ${\displaystyle {\sqrt {3}}}$

Une solution non optimale au problème du voyageur de commerce peut avoir des croisements, mais il est possible d'éliminer tous les croisements par des étapes d'optimisation locales qui réduisent la longueur totale. En utilisant des étapes qui éliminent également les croisements à chaque étape, cela peut être fait en temps polynomial , mais sans cette restriction, il existe des séquences d'optimisation locales qui utilisent à la place un nombre exponentiel d'étapes.

Le tour bitonique le plus court (le polygone monotone de périmètre minimum passant par les points donnés) est toujours une polygonalisation et peut être trouvé en temps polynomial.

Compte

Le problème de comptage de toutes les polygonalisations d'un ensemble de points donné appartient à #P , la classe des problèmes de comptage associés aux problèmes de décision dans NP . Cependant, on ne sait pas s'il est #P-complet ou, sinon, quelle pourrait être sa complexité de calcul. Un ensemble de points a exactement une polygonalisation si et seulement s'il est en position convexe . Il existe des ensembles de points pour lesquels le nombre de polygonalisations est aussi grand que , et chaque ensemble de points a au plus des polygonalisations. ${\displaystyle n}$${\displaystyle 4.64^{n}}$${\displaystyle n}$${\displaystyle 54.6^{n}}$

Les méthodes appliquant le théorème du séparateur planaire aux triangulations étiquetées des points peuvent être utilisées pour compter toutes les polygonalisations d'un ensemble de points en temps sous-exponentiel, . La programmation dynamique peut être utilisée pour compter toutes les polygonalisations monotones en temps polynomial, et les résultats de ce calcul peuvent ensuite être utilisés pour générer une polygonalisation monotone aléatoire. ${\displaystyle n}$${\displaystyle n^{O({\sqrt {n}})}}$

Génération

Un polygone qui ne peut pas être transformé en un autre polygone passant par les mêmes points par des flips ou des VE-flips

On ne sait pas s'il est possible pour le système de toutes les polygonalisations de former un espace d'états connexe sous des mouvements locaux qui modifient un nombre limité d'arêtes des polygonalisations. Si cela était possible, il pourrait être utilisé dans le cadre d'un algorithme pour générer toutes les polygonalisations, en appliquant un parcours de graphe à l'espace d'état. Pour ce problème, il est insuffisant de considérer des flips qui suppriment deux arêtes d'une polygonalisation et les remplacent par deux autres arêtes, ou des VE-flips qui suppriment trois arêtes, dont deux partagent un sommet, et les remplacent par trois autres arêtes. Il existe des polygonalisations pour lesquelles aucun flip ou VE-flip n'est possible, même si le même ensemble de points a d'autres polygonalisations.

Les enveloppes polygonales , polygones faiblement simples qui utilisent chaque point donné une ou plusieurs fois comme sommet, incluent toutes les polygonalisations et sont reliées par des déplacements locaux. Une autre classe plus générale de polygones, les polygones environnants , sont de simples polygones qui ont certains des points donnés comme sommets et englobent tous les points. Ils sont à nouveau connectés localement et peuvent être répertoriés en temps polynomial par polygone. L'algorithme construit un arbre de polygones, avec la coque convexe comme racine et avec le parent de chaque autre polygone environnant obtenu en supprimant un sommet (ce qui s'est avéré possible en appliquant le théorème des deux oreilles à l'extérieur du polygone). Il applique ensuite un algorithme de recherche inversée à cet arbre pour lister les polygones. Grâce à cette méthode, toutes les polygonalisations peuvent être répertoriées en temps exponentiel ( pour les points) et en espace polynomial . ${\displaystyle 2^{O(n)}}$${\displaystyle n}$

Applications

Les puzzles classiques de connexion des points impliquent de connecter des points en séquence pour former une forme inattendue, souvent sans croisements. Le problème du voyageur de commerce et ses variantes ont de nombreuses applications. La polygonalisation a également des applications dans la reconstruction des courbes de niveau à partir de points de données dispersés et dans le traçage des limites dans l'analyse d'images .

Voir également

• Théorème de Denjoy-Riesz , sur des ensembles d'une infinité de points pouvant être reliés par un arc de Jordan

Les références