2010-04-29 19 views
15

¿Cuál es el mejor algoritmo para encontrar si tres puntos son colineales en un conjunto de puntos, digamos n? Por favor, también explique la complejidad si no es trivial.Dado un conjunto de puntos, encuentre si alguno de los tres puntos es colineal

Gracias
Bala

+1

¿Es esta su tarea? – WhirlWind

+2

Esta pregunta fue discutida en la clase y sé el algoritmo O (N^2). Encontré un algoritmo bastante simple para hacerlo en O (N^2). Quiero saber si hay un algoritmo aún más simple. – Boolean

+0

¿Son estos 2d puntos? –

Respuesta

15

Si puede encontrar un algoritmo mejor que O (N^2), puede publicarlo.

Este problema es 3-SUM Hard, y si hay un algoritmo sub-cuadrático (es decir, mejor que O (N^2)) porque es un problema abierto. Se ha demostrado que muchos problemas comunes de geometría computacional (incluido el suyo) son 3SUM y esta clase de problemas está creciendo. Al igual que NP-Hardness, el concepto de 3SUM-Hardness ha demostrado ser útil para probar la "dureza" de algunos problemas.

Para una prueba de que su problema es 3SUM duro, se refieren a la excelente papel Surver aquí: http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf

Su problema aparece en la página 3 (convenientemente llamada 3-PUNTOS-ON-LINE) en el documento mencionado anteriormente.

Por lo tanto, el algoritmo actualmente más conocido es O (n^2) y ya lo tienes :-)

+0

Gracias @Moron. El enlace fue muy útil. – Boolean

+0

@Moron - ¿hay un algoritmo con el tiempo 'O (n^2)' que no está utilizando la tabla hash como la descrita por @Strilanc? –

+1

@Elazar: Creo que es posible, al considerar el doble en el que las líneas se mapean en puntos y viceversa (a, b) <-> y = ax + b. Ahora el problema corresponde a encontrar vértices en el dual con un grado de al menos 6. Aparentemente esto es posible en O (n^2) tiempo y O (n^2) espacio. Este libro: http://books.google.com/books?id=PBRJ-ruwOQcC tiene una mención al respecto en la página 94. –

6

A O sencillo (d * N^2) tiempo y algoritmo de espacio, donde d es la dimensionalidad y N es el número de puntos (probablemente no óptimo):

  • Crear un cuadro delimitador alrededor del conjunto de puntos (hacerlo lo suficientemente grande para que no haya puntos en el límite)
  • Para cada par de puntos, calcule la línea que pasa por ellos.
  • Para cada línea, calcule sus dos puntos de colisión con el cuadro delimitador.
  • Los dos puntos de colisión definen la línea original, por lo que si hay líneas coincidentes, también producirán los mismos dos puntos de colisión.
  • Use un conjunto de almohadillas para determinar si hay pares de puntos de colisión duplicados.
  • Hay 3 puntos colineales si y solo si hubo duplicados.
+0

Su condición es necesaria, pero ¿es suficiente? Pon 4 puntos en (0,0), (0,1), (1,0) y (1,1) para definir el cuadro delimitador. El par [(0.5,0.6), (0.5,0.7)] crea un segmento que interseca el cuadro en (0.5,0), al igual que el par [(0.4,0.1), (0.3,0.2)]. Sin embargo, no hay tres de los 8 puntos en una línea común. – Eric

+1

Es una condición suficiente porque dos puntos definen una línea. Solo ha considerado uno de los puntos en el par de puntos de colisión; el otro será diferente, por lo que el par no coincide. –

+1

Tienes razón. Es posible que desee dar más detalles, en el paso 2, para aclarar que los dos puntos de colisión se unen para crear un "par de puntos de colisión". De lo contrario, un lector puede confundir el par (de puntos de colisión) en el paso 3 con el par (de puntos originales) en el paso 2, como hice yo. – Eric

4

Otra solución simple (tal vez incluso trivial) que no utiliza una tabla hash, se ejecuta en O (n log n), y usa o (n) espacio:

vamos S ser un conjunto de puntos, vamos a describir un algoritmo que se entera de si es o no S contiene unos tres puntos alineados.

  1. Para cada punto de o en S hacer:
    1. pasar una paralelo línea L a la x eje x a través de o.
    2. Reemplace cada punto en S debajo de L, con su reflejo. (Por ejemplo, si L es el eje x, (a,-x) para x>0 se convertirá en (a,x) después de la reflexión).Deje que el nuevo conjunto de puntos sea S'
    3. El ángulo de cada punto p en S', es el ángulo derecho del segmento po con la línea L. Vamos a ordenar los puntos S' por sus ángulos.
    4. Camine por los puntos ordenados en S'. Si hay dos puntos consecutivos que son colineales con o - devuelve verdadero.
  2. Si no se encontraron puntos colineales en el ciclo - devuelve falso.

El ciclo ejecuta n veces, y cada iteración realiza nlog n pasos. No es difícil probar que si hay tres puntos en una línea los encontrarán, y no encontraremos nada de lo contrario.

+0

Solo necesita hacer el ciclo externo para la mitad de los puntos: los que tienen 'y' más grande valores de coordenadas, ¿correcto? Además, cuando dijiste "hay dos puntos consecutivos que son colineales", en realidad querías decir "hay dos puntos consecutivos que son colineales junto con el punto 'o'", ¿te entiendo correctamente? –

+1

La primera observación es correcta, aunque no cambia la complejidad. Hacerlo para la otra mitad de los puntos es equivalente debido a la simetría. Tenga en cuenta que primero tiene que ordenarlos, lo que hace que el algoritmo sea un poco más complejo. El segundo punto también es correcto, corrigiéndolo, Gracias. –

Cuestiones relacionadas