Tester si un ensemble de n points dans le plan forme un polygone n convexe en temps o (nlogn)

Supposons que l'on vous donne un ensemble de n points dans le plan et que vous souhaitez vérifier s'ils forment un polygone n convexe, c'est-à-dire s'ils se trouvent tous sur la coque convexe. Je me demandais si quelqu'un savait comment faire cela en temps o (nlogn), c'est-à-dire sans calculer le CH.

cg.comp-geom Babis Tsourakakis
la source

Vous pouvez calculer la coque convexe en temps O (n log n). Voulez-vous dire s'il est possible de le faire en moins de temps que cela?

Per Vognsen

oui, je crois qu'il devrait y avoir un algorithme de temps linéaire pour ce problème. mais je ne sais pas comment

Babis Tsourakakis

Il a écrit o (nlogn) et non O (nlogn), donc sa question est correcte.

Shiva Kintali

J'utilise la petite notation o donc la question est toujours la même

Babis Tsourakakis

Cela me fait froncer les sourcils un peu de voir le tri des nombres (ou des coques convexes équivalentes de points cartésiens) déclaré comme prenant du temps Θ (n log n) sans une déclaration explicite du modèle de calcul que vous utilisez. Le tri par comparaison prend Θ (n log n) temps mais le modèle de comparaison ne permet même pas du tout de calculer les coques. Ils sont tous deux encore Θ (n log n) temps pour les arbres de décision algébriques (comme le montre la réponse acceptée), mais plus rapides dans les modèles de calcul qui ressemblent plus aux ordinateurs réels.

David Eppstein

Réponses:

Cela semble peu probable, du moins dans les modèles d'arbre de comparaison / algébrique. Définition d'abord:

Un point de consigne est en position convexe si aucun point de peut être écrite comme une combinaison convexe des points restants de . $P$ $P$ $P$

Maintenant, décider si un ensemble de nombres sont tous distincts prend du temps (c'est ce qu'on appelle l'unicité). Étant donné un tel ensemble de nombres , mappez-les à l'ensemble des points $n$ $\Omega(n \log n)$ $n$ $X$ S'il n'y a pas de nombre répété, alors les points sont en position convexe.

P = {(x, x^{2}) | x \in X} .

$P = \{ (x, x^2) | x \in X\}.$

S'il y a un nombre répété, alors ce nombre répété correspond à un point qui peut être écrit comme une combinaison convexe des points restants. A savoir, les points ne sont pas en position convexe.

À savoir, décider si un ensemble de points est en position convexe est aussi difficile que l'unicité.

Sariel Har-Peled
la source

Il existe une variante de cette réduction qui ne produit pas de points en double. Soit X [1..n] un ensemble d'entiers; tester si tous les éléments de X sont distincts nécessite encore du temps Ω (n log n) dans le modèle d'arbre de décision algébrique. Remplacez maintenant chaque entier

X [i]

$X[i]$ par le point

. Si le tableau d'origine X a des doublons, les points résultants auront au moins un point à l'intérieur de la coque convexe; sinon, les points sont en position convexe.

(X [i], X [i]^{2} + i / n^{2})

$(X[i], X[i]^2+i/n^2)$

Jeffε

@Babis: la réduction de Jeff fonctionne lorsque les points en double ne sont pas autorisés. Les points générés par la réduction sont uniques quelle que soit la matrice initiale.

Vinayak Pathak

On obtient ainsi que le nombre des coins de la coque convexe est égal à n si et seulement si deux points n'ont pas la même coordonnée x. Merci beaucoup, au début, je pensais que cela devrait être plus facile que le tri.

Babis Tsourakakis

Merci Vinayak, je n'avais pas vu la réduction de Jeff depuis qu'elle a été publiée en même temps que j'écrivais le commentaire précédent que j'ai remplacé par ce qui précède

Babis Tsourakakis

Bien sûr, je ne suis pas d'accord avec l'expression "modèle standard". C'est exactement ce qu'est la Word RAM :) C'est le modèle qui correspond le mieux à un vrai ordinateur et que nous utilisons pour analyser l'algorithme dans la plupart des TCS. La géométrie a plaidé une exception pour utiliser la vraie RAM afin que nous n'ayons pas besoin de traiter des problèmes de précision. Mais ce n'est pas "le modèle standard".

Mihai

-1

$O(n log n)$

Une fois que vous connaissez l'ordre des points, l'angle de chaque point au point suivant de la séquence doit être monotone. Cela constitue une condition nécessaire et, je pense, suffisante.

Obtenir le point intérieur est laissé comme un exercice pour le lecteur.

Edit: Comme une première passe à une simple démonstration de $O(n log n)$

BCS
la source

Vous avez probablement mal lu son o (n log n) comme O (n log n) autant que moi. Quoi qu'il en soit, l'algorithme que vous avez décrit est un emballage cadeau sous forme embryonnaire. Vous n'avez pas réellement besoin d'utiliser un point intérieur; vous pouvez utiliser un point sur la frontière, par exemple un point avec une coordonnée x minimale.

Per Vognsen

O (n l o g n)

$O(n log n)$

o ()

$o()$

Le fait est qu'il existe de nombreux algorithmes de coque convexes qui s'exécutent en O (n log n). Votre algorithme est essentiellement un ancien emballage cadeau. Il demandait quelque chose de plus rapide, par exemple du temps linéaire. Voir les autres réponses.

Per Vognsen

Concernant votre modification, si vous pouviez regarder la réponse acceptée au-dessus de la vôtre, vous verrez que le problème est équivalent à l'unicité des éléments, qui a une limite inférieure O (n log n).

Per Vognsen

@BCS: Je crains que vous ne compreniez mal la réponse de Sariel Har-Peled. La réduction est de l'unicité au test de position convexe, pas dans l'autre sens. Autrement dit, Sariel (et JeffE) a déclaré que si vous recevez un ensemble de nombres et que vous souhaitez tester l'unicité, vous pouvez le convertir en un ensemble de points et utiliser n'importe quel algorithme pour les tests de position convexe.

Tsuyoshi Ito