Dado un conjunto de puntos, encuentre si alguno de los tres puntos es colineal

Question

¿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.

Gracias
Bala

Answer 1

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 :-)

Answer 2

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.

Answer 3

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.