Prueba de si un conjunto de n puntos en el plano forma un polígono n convexo en el tiempo o (nlogn)

Suponga que tiene un conjunto de n puntos en el plano y desea verificar si forman un polígono convexo n, es decir, si todos se encuentran en el casco convexo. Me preguntaba si alguien sabe cómo hacer esto en o (nlogn) tiempo, es decir, sin calcular el CH.

cg.comp-geom Babis Tsourakakis
fuente

Puede calcular el casco convexo en tiempo O (n log n). ¿Quieres decir si es posible hacerlo en menos tiempo que eso?

Por Vognsen

Sí, creo que debería haber algún algoritmo de tiempo lineal para este problema. pero no sé cómo

Babis Tsourakakis

Escribió o (nlogn) no O (nlogn), por lo que su pregunta es correcta.

Shiva Kintali

Uso la pequeña notación o para que la pregunta siga vigente tal como está

Babis Tsourakakis, el

Me hace fruncir un poco el ceño al ver que la ordenación de números (o cascos convexos equivalentes de puntos cartesianos) indica que toma tiempo Θ (n log n) sin una declaración explícita de qué modelo de cálculo está utilizando. La clasificación por comparación lleva Θ (n log n) tiempo, pero el modelo de comparación ni siquiera permite que se calculen los cascos. Ambos todavía son Θ (n log n) tiempo para árboles de decisión algebraicos (como muestra la respuesta aceptada), pero más rápidos en modelos de computación que se parecen más a las computadoras reales.

David Eppstein

Respuestas:

Eso parece poco probable, al menos en los modelos de árbol de comparación / algebraico. Definición primero:

Un conjunto de puntos está en posición convexa si ningún punto de puede ser escrita como una combinación convexa de los puntos restantes de . $P$ $P$ $P$

Ahora, decidir si un conjunto de números son todos distintos lleva tiempo (esto se conoce como UNIQUENESS). Dado tal conjunto de números , mapearlos al conjunto de puntos Si no hay un número repetido, los puntos están en posición convexa. $n$ $\Omega(n \log n)$ $n$ $X$

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

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

Si hay un número repetido, entonces este número repetido corresponde a un punto que puede escribirse como una combinación convexa de los puntos restantes. Es decir, los puntos no están en posición convexa.

A saber, decidir si un conjunto de puntos está en posición convexa es tan difícil como UNIQUENESS.

Sariel Har-Peled
fuente

X [i]

$X[i]$

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

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

@Babis: la reducción de Jeff funciona cuando no se permiten puntos duplicados. Los puntos generados por la reducción son únicos sin importar cuál sea la matriz inicial.

Vinayak Pathak

De este modo, obtenemos que el número de esquinas del casco convexo es igual a n si y solo si no hay dos puntos que tengan la misma coordenada x. Muchas gracias, inicialmente pensé que debería ser más fácil que ordenar.

Babis Tsourakakis

Gracias Vinayak, no había visto la reducción de Jeff desde que se publicó al mismo tiempo cuando estaba escribiendo el comentario anterior que sustituí por el anterior

Babis Tsourakakis, el

Claro, no estoy de acuerdo con la frase "modelo estándar". Eso es exactamente lo que es la RAM de Word :) Es el modelo que más se acerca a una computadora real y que usamos para analizar algoritmos en la mayoría de TCS. La geometría ha alegado una excepción para usar la RAM real para que no tengamos que lidiar con problemas de precisión. Pero ese no es "el modelo estándar".

Mihai

-1

Si asume que todos los puntos están en el casco convexo y puede encontrar un punto que está dentro del casco convexo, puede encontrar el orden de los puntos en $O(n log n)$

Una vez que conoce el orden de los puntos, el ángulo desde cada punto hasta el siguiente punto de la secuencia debe ser monótono. Esto forma una condición necesaria y, creo, suficiente.

Obtener el punto interior se deja como un ejercicio para el lector.

$O(n log n)$

BCS
fuente

Probablemente leyó mal su o (n log n) como O (n log n) tanto como yo. De todos modos, el algoritmo que describió es envoltura de regalos en forma embrionaria. En realidad no necesitas usar un punto interior; puede usar un punto en el límite, por ejemplo, un punto con una coordenada x mínima.

Por Vognsen

O (n l o g n)

$O(n log n)$

o ()

$o()$

El punto es que hay muchos algoritmos de casco convexo que se ejecutan en O (n log n). Su algoritmo es básicamente una envoltura de regalos antigua. Estaba pidiendo algo más rápido, por ejemplo, tiempo lineal. Ver las otras respuestas.

Por Vognsen

Con respecto a su edición, si pudiera ver la respuesta aceptada sobre la suya, verá que el problema es equivalente a la unicidad del elemento, que tiene un límite inferior O (n log n).

Por Vognsen

@BCS: Me temo que tienes algunos malentendidos sobre la respuesta de Sariel Har-Peled. La reducción es de unicidad a prueba de posición convexa, no en la otra dirección. Es decir, Sariel (y JeffE) declararon que si se le da un conjunto de números y desea probar la unicidad, puede convertirlo en un conjunto de puntos y usar cualquier algoritmo para la prueba de posición convexa.

Tsuyoshi Ito