algorithm - tabla - infracciones que quitan puntos 2017

Encuentra una línea que pase el número máximo de puntos

Question

Encontré una pregunta de Google Entrevista sobre CareerCup

Dado un plano 2D, supongamos que hay alrededor de 6000 puntos en él. Encuentra una línea que pase la mayor cantidad de puntos.

Muchas respuestas dicen que esta pregunta es difícil e involucra algún tipo de algoritmo especial.

Pero mi punto de vista es diferente y tal vez estoy equivocado.

Aquí está mi pensamiento:

Primero daré un sistema de ejes al plano 2D. Por lo tanto, cada punto tendrá su único xey, es decir, {x, y} . Para simplificar, podemos poner el sistema del eje {0, 0} como la parte inferior izquierda del plano completo y, por lo tanto, cada xey son más grandes que 0.

Entonces tengo una teoría:

Si varios puntos están en la misma línea, entonces debe estar en uno de los 3 casos siguientes:

1. sus valores x son los mismos
2. sus valores y son los mismos
3. sus valores x/y o y/x son los mismos. Pero el caso x/y es lo mismo que el caso y/x , así que centrémonos en x/y .

Entonces tendré 3 hashtables.

1. El primero ( hashtable-x ) está con la clave de x , el valor es la lista de puntos que tienen la misma x ;

2. el segundo ( hashtable-y ) está con la clave de y y el valor es la lista de puntos que tienen la misma y ;

3. el último ( hashtable-xy ) está con la clave de x/y y el valor es la lista de puntos que tienen el mismo x/y ;

Luego escaneo los 6000 puntos, para cada punto, obtendré su x de hashtable-x , y pongo el punto en el valor (una lista) de esa ranura; luego haré cosas similares a hashtable-y y hashtable-xy .

Finalmente, analizaré todas las listas en las 3 tablas hash y encontraré que la lista más larga contendrá los puntos de la línea deseada.

¿Cómo piensas en mi algoritmo?

Ok, aquí está el duplicado, siento no haber encontrado esa pregunta antes.

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

Answer 1

Su algoritmo no funcionará como se indica. Considere que muchos puntos caen en la línea y = 2x + 1, lo que significa que obtiene (1,3), (2,5), (3,7), (4,9) y (5,11).

No creo que se espera que resuelva esto a menos que tenga un curso de posgrado en geometría computacional. El trato consiste en convertir todos los puntos en líneas en el espacio dual, utilizando la dualidad punto-línea y encontrar el punto en el que la mayoría de las líneas se cruzan. Ingenuamente puedes hacer esto en O (n ^ 2) pasando por cada par de líneas y evaluando dónde se cruzan en forma analítica. También creo que puedes hacer O (n log n) usando algoritmos de estilo de barrido plano, pero no estoy seguro de los detalles.

Answer 2

Voy a suponer que el número de puntos es mayor o igual a 2 aquí en mi respuesta (cero y un punto son casos triviales).

Primero note que cualquier línea debe pasar por al menos dos de los puntos. Entonces, podemos construir una solución de la siguiente manera:

for each pair of points p1,p2
    find equation of the line l passing through p1,p2

    for each point p3 not p1 or p2
        if p3 lies on l
            counter[l]++

return argmax(counter)