¿Cuál es el algoritmo más eficiente para encontrar una línea recta que atraviesa la mayoría de los puntos?

Question

El problema:

N puntos se dan en un plano bidimensional. ¿Cuál es el número máximo de puntos en la misma línea recta?

El problema tiene solución O (N): pase por cada punto y encuentre el número de puntos que tienen el mismo dx/dy con relación al punto actual. Almacene las relaciones dx/dy en un mapa hash para mayor eficiencia.

¿Hay una mejor solución a este problema que O (N)?

Answer 1

No es probable ninguna solución a este problema que es significativamente mejor que O (n^2) en un modelo estándar de la computación .

El problema de encontrar tres puntos colineales reduce el problema de encontrar la línea que atraviesa la mayor cantidad de puntos, y encontrar tres puntos colineales es 3SUM-hard, es decir, resolverlo en menos de O (n^2) tiempo sería un gran resultado teórico.

Consulte el previous question para encontrar tres puntos colineales.

Para su referencia (usando la prueba conocida), supongamos que queremos responder un problema 3SUM como encontrar x, y, z en la lista X tal que x + y + z = 0. Si tuviéramos un algoritmo rápido para el problema del punto colineal, podríamos usar ese algoritmo para resolver el problema 3SUM de la siguiente manera.

Para cada x en X, cree el punto (x, x^3) (por ahora suponemos que los elementos de X son distintos). Luego, verifique si existen tres puntos colineales entre los puntos creados.

ver que esto funciona, en cuenta que si x + y + z = 0, entonces la pendiente de la línea de x a y es

(y^3 - x^3)/(y - x) = y^2 + yx + x^2

y la pendiente de la línea de x a z es

(z^3 - x^3)/(zx) = z^2 + zx + x^2 = (- (x + y))^2 - (x + y) x + x^2 = x^2 + 2xy + y^2 - x^2 - xy + x^2 = y^2 + yx + x^2

Por el contrario, si la pendiente de x a y es igual a la pendiente de xt oz entonces

y^2 + yx + x^2 = z^2 + zx + x^2,

que implica que

(y - z) (x + y + z) = 0,

por lo tanto y = z o z = -x - y basta para demostrar que la reducción es válida.

Si hay duplicados en X, primero comprueba si x + 2y = 0 para cualquier elemento x y duplicado y (en tiempo lineal usando hashing o O (n lg n) tiempo usando sorting), y luego elimina los duplicados antes de reducir al problema colineal de búsqueda de puntos.

Answer 2

Si limita el problema a las líneas que pasan por el origen, puede convertir los puntos en coordenadas polares (ángulo, distancia desde el origen) y ordenarlos por ángulo. Todos los puntos con el mismo ángulo se encuentran en la misma línea. O (n logn)

No creo que haya una solución más rápida en el caso general.

Answer 3

Esto no es una solución mejor que O (n^2), pero se puede hacer lo siguiente,

1. Para cada punto de convertir primero convertirlo como si donde en el (0,0) de coordenadas , y luego haga la traducción equivalente para todos los otros puntos moviéndolos la misma distancia x, y que necesita para mover el punto elegido original.

2.Traducir este nuevo conjunto de puntos traducidos al ángulo con respecto al nuevo (0,0).

3.Mantenga almacenado el número máximo (MSN) de los puntos que están en cada ángulo.

4.Choose el máximo número almacenado (MSN), y que va a ser la solución

Answer 4

El Hough Transform puede darle una solución aproximada. Es aproximado porque la técnica de binning tiene una resolución limitada en el espacio de parámetros, por lo que el bin máximo le dará un rango limitado de líneas posibles.

Answer 5

Es poco probable para un $ o algoritmo (n^2) $ de existir, ya que el problema (de incluso Verificando 3 puntos en R^2 son colineales) es 3sum-duro (http://en.wikipedia.org/wiki/3SUM)

Answer 6

De nuevo una solución O (n^2) con pseudo código. Idea es crear una tabla hash con la línea misma como clave. La línea se define por la pendiente entre los dos puntos, el punto donde la línea corta el eje xy el punto donde la línea corta el eje y.

La solución presupone lenguajes como Java, C# donde los métodos equals y los métodos de código hash del objeto se utilizan para la función hash.

Crear un objeto (llamada SlopeObject) con 3 campos

1. Slope // Puede ser infinito
2. Punto de interceptación con el eje x - poix // será (Infinity, algunos y valor) o (valor x, 0)
3. Count

poix habrá un par de puntos (x, y). Si la línea cruza el eje x, el poix lo hará (algún número, 0). Si la línea es paralela al eje x, entonces poix = (Infinito, algún número) donde el valor y es donde la línea cruza el eje y. Ignorar es igual a método donde 2 objetos son iguales si Slope y poix son iguales.

Hashcode se reemplaza con una función que proporciona código hash basado en combinación de valores de Slope y poix.Algunos pseudo código de abajo

Hashmap map; 
foreach(point in the array a) { 
    foeach(every other point b) { 
     slope = calculateSlope(a, b); 
     poix = calculateXInterception(a, b); 
     SlopeObject so = new SlopeObject(slope, poix, 1); // Slope, poix and intial count 1. 
     SlopeObject inMapSlopeObj = map.get(so); 
     if(inMapSlopeObj == null) { 
      inMapSlopeObj.put(so); 
     } else { 
      inMapSlopeObj.setCount(inMapSlopeObj.getCount() + 1); 
     } 
    } 
} 
SlopeObject maxCounted = getObjectWithMaxCount(map); 
print("line is through " + maxCounted.poix + " with slope " + maxCounted.slope); 

Answer 7

Como ya se ha mencionado, probablemente no es una forma de resolver el caso general de este problema mejor que O (n^2). Sin embargo, si supone que una gran cantidad de puntos se encuentran en la misma línea (digamos que la probabilidad de que un punto aleatorio en el conjunto de puntos se encuentre en la línea con el número máximo de puntos es p) y no necesita un algoritmo exacto, un algoritmo aleatorizado es más eficiente.

maxPoints = 0 
Repeat for k iterations: 
    1. Pick 2 random, distinct points uniformly at random 
    2. maxPoints = max(maxPoints, number of points that lies on the 
     line defined by the 2 points chosen in step 1) 

Tenga en cuenta que en el primer paso, si has elegido 2 puntos que se encuentra en la línea con el número máximo de puntos, obtendrá la solución óptima. Suponiendo que n es muy grande (es decir, podemos tratar la probabilidad de encontrar 2 puntos deseables como muestreo con reemplazo), la probabilidad de que esto ocurra es p^2. Por lo tanto, la probabilidad de encontrar una solución subóptima después de k iteraciones es (1 - p^2)^k.

Supongamos que puede tolerar una tasa de frecuencias negativas falsas = err. Entonces este algoritmo se ejecuta en O (nk) = O (n * log (err)/log (1 - p^2)). Si tanto n como p son lo suficientemente grandes, esto es significativamente más eficiente que O (n^2). (es decir, supongamos n = 1,000,000 y usted sabe que hay al menos 10,000 puntos que se encuentran en la misma línea. Entonces se necesitaría n^2 en la magnitud de 10^12 operaciones, mientras que el algoritmo aleatorizado requeriría la magnitud de 10^9 operaciones para obtener un índice de error de menos de 5 * 10^-5.)