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

"computational geometry an introduction"

Question

El problema:

Los puntos N 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 una solución O (N ² ): recorra 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 solución mejor para este problema que O (N ² )?

Answer 1

Como ya se mencionó, probablemente no haya una manera de resolver el caso general de este problema mejor que O (n ^ 2). Sin embargo, si asume que hay un gran número de puntos en la misma línea (diga 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 aleatorio 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 escogió 2 puntos que se encuentran 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 tasa de falso negativo = 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, Supuesto n = 1,000,000 y usted sabe que hay al menos 10,000 puntos que se encuentran en la misma línea. Entonces n ^ 2 se requeriría en la magnitud de las operaciones de 10 ^ 12, mientras que el algoritmo aleatorio requeriría la magnitud de las operaciones de 10 ^ 9 para obtener una tasa de error de menos de 5 * 10 ^ -5.)

Answer 2

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

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

Crear un objeto (llamada SlopeObject) con 3 campos

1. Pendiente // Puede ser infinito
2. Punto de intercepción con el eje x - poix // Será (Infinito, algún valor y) o (valor x, 0)
3. Contar

poix será un punto (x, y) par. Si la línea cruza el eje x, la poix hará (algún número, 0). Si la línea es paralela al eje x, entonces poix = (Infinito, algún número) donde y el valor es donde la línea cruza el eje y. La anulación es igual al método donde 2 objetos son iguales si Slope y poix son iguales.

El código hash está anulado con una función que proporciona código hash basado en la combinación de valores de Slope y poix . Algunos pseudo codigos 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 3

Es poco probable que exista un algoritmo $ o (n ^ 2) $, ya que el problema (de incluso verificar si 3 puntos en R ^ 2 son colineales) es 3Sum-hard ( http://en.wikipedia.org/wiki/3SUM )

Answer 4

Es probable que no haya una solución a este problema que sea significativamente mejor que O (n ^ 2) en un modelo estándar de cálculo.

El problema de encontrar tres puntos colineales se reduce al problema de encontrar la línea que pasa por la mayoría de los puntos, y encontrar tres puntos colineales es 3SUM-duro, lo que significa que resolverlo en menos de O (n ^ 2) el tiempo sería un gran problema. Resultado teórico.

Vea la pregunta anterior sobre la búsqueda de tres puntos colineales.

Para su referencia (usando la prueba conocida), suponga que queremos responder a un problema de 3SUM, como encontrar x, y, z en la lista X, de modo 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). A continuación, compruebe si existen tres puntos colineales entre los puntos creados.

Para ver que esto funciona, tenga 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 recta de x a z es

(z ^ 3 - x ^ 3) / (z - x) = 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

A la inversa, si la pendiente de x a y es igual a la pendiente de x a z, entonces

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

lo que implica que

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

así que y = z o z = -x - y como suficiente para probar que la reducción es válida.

Si hay duplicados en X, primero verifique si x + 2y = 0 para cualquier x y el elemento duplicado y (en tiempo lineal usando hashing u O (n lg n) usando clasificación), y luego elimine los duplicados antes de reducir a Problema colineal de búsqueda de puntos.

Answer 5

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

1. Para cada punto, primero conviértalo como si estuviera en la coordenada (0,0), y luego realice la traducción equivalente para todos los demás puntos moviéndolos a la misma x, y distancia que necesitaba para mover el punto elegido original.

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

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

4.Elija el número máximo almacenado (MSN), y esa será la solución

Answer 6

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

Answer 7

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