Partición triangular

Question

Esto fue un problema en el concurso Pacific ACM-ICPC 2010. La esencia de esto es tratar de encontrar una manera de dividir un conjunto de puntos dentro de un triángulo en tres subtriángulos de modo que cada partición contenga exactamente un tercio de los puntos.

de entrada:

• coordenadas de un triángulo de delimitación: (v1x,v1y),(v2x,v2y),(v3x,v3y)
• Un número 3n < 30000 representa el número de puntos que se encuentran dentro del triángulo
• coordenadas de los 3n puntos: (x_i,y_i) para i=1...3n

de salida:

• Un punto (sx,sy) que divide el triángulo en 3 subtriángulos tal que cada subtriangulo contiene exactamente n puntos.

La forma en que el punto de división divide el triángulo delimitador en subtriángulos es la siguiente: Dibuje una línea desde el punto de división a cada uno de los tres vértices. Esto dividirá el triángulo en 3 subtriángulos.

Tenemos la garantía de que existe tal punto. Cualquier punto de ese tipo será suficiente (la respuesta no es necesariamente única).

Aquí hay un ejemplo del problema de n=2 (6 puntos). Se nos dan las coordenadas de cada uno de los puntos coloreados y las coordenadas de cada vértice del triángulo grande. El punto de división está marcado con un círculo en gris.

Puede alguien sugerir un algoritmo más rápido que O(n^2)?

Answer 1

Aquí hay un algoritmo O(n log n). Supongamos que no hay degeneración.

La idea de alto nivel es, dado un triángulo PQR,

P 
    C \ 
/S\ 
R-----Q 

inicialmente que sitúe el punto de C centro en P. Deslice C hacia R hasta que haya n puntos dentro del triángulo CPQ y uno (S) en el segmento CQ. Deslice C hacia Q hasta que el triángulo CRP ya no sea deficiente (perturbar C y listo) o CP alcance un punto. En este último caso, deslice C lejos de P hasta que el triángulo CRP ya no es deficiente (que hemos terminado) o CQ llega a un punto, en cuyo caso comenzamos deslizamiento hacia CQ nuevo.

Es evidente que la aplicación no puede puntos “Slide”, por lo que para cada triángulo que implica C, para cada vértice S de ese triángulo que no sea C, almacenar los puntos dentro del triángulo en un árbol binario de búsqueda ordenados por ángulo con S. Estas estructuras son suficientes para implementar este algoritmo cinético.

Afirmo sin pruebas que este algoritmo es correcto.

En cuanto al tiempo de ejecución, cada evento es una intersección de punto y puede manejarse en el tiempo O(log n). Los ángulos PC y QC y RC son monótonos, por lo que cada una de las líneas O(1) llega a cada punto como máximo una vez.

Answer 2

Aquí hay un enfoque que toma O (log n) pasadas de costo n cada una.

Cada pasada comienza con un punto inicial, que divide el triángulo en sus subtriangles. Si cada uno tiene n puntos, hemos terminado. De lo contrario, considere el subcultivo que está más alejado del n deseado. Supongamos que tiene demasiados, solo por ahora. Los desequilibrios suman cero, por lo que al menos uno de los otros dos triángulos tiene muy pocos puntos. El tercer sub-triángulo también tiene muy pocos, o tiene exactamente n puntos, o el sub-triángulo original no tendría la discrepancia más alta.

Tome el sub-triángulo más desbalanceado y considere mover el punto central a lo largo de la línea que se aleja de él. Al hacerlo, el desequilibrio del punto más desequilibrado se reducirá. Para cada punto en el triángulo, puedes calcular cuándo ese punto se cruza dentro o fuera del sub-triángulo más desequilibrado a medida que mueves el punto central. Por lo tanto, puede hacer ejercicio en el tiempo n donde mover el punto central para dar al triángulo más desequilibrado el recuento deseado.

Al mover el punto central puede elegir si los puntos se mueven fuera del sub-triángulo más desequilibrado, pero no puede elegir a cuál de los otros dos subtrángulos van, o desde, pero puede predecir con qué facilidad desde qué lado de la línea se está deslizando el punto central en que viven, de modo que puede mover el punto central a lo largo de esta línea para obtener la discrepancia máxima más baja después del movimiento. En el peor de los casos, todos los puntos movidos entran o salen del subcultivo que estaba exactamente equilibrado. Sin embargo, si el sub-triángulo desequilibrado tiene n + k puntos, moviendo k/2 de ellos, puede mover, en el peor de los casos, al caso en que él y el sub-triángulo previamente balanceado están fuera por k/2. El tercer subcultivo puede estar desequilibrado hasta k, en la otra dirección, pero en este caso un segundo pase reducirá el desequilibrio máximo a algo por debajo de k/2.

Por lo tanto, en el caso de un gran desequilibrio, podemos reducirlo al menos un factor constante en dos pasadas del algoritmo anterior, por lo que en O (log n) el desequilibrio será lo suficientemente pequeño como para que podamos casos en los que nos preocupamos por un exceso de como máximo un punto. Aquí voy a adivinar que el número de casos especiales es prácticamente enumerable en un programa, y ​​el costo equivale a una pequeña adición constante.

Answer 3

La idea principal es: si tenemos la línea, podemos tratar de encontrar un punto con la búsqueda lineal. Si la línea no es lo suficientemente buena, podemos moverla usando la búsqueda binaria.

1. Ordenar las puntos basado en la dirección desde el vértice A. Ordenarlos por B y C también.
2. Establezca el rango actual para el vértice A en todos los puntos.
3. Seleccione 2 puntos medios del rango para el vértice A. Estos 2 puntos definen subrango para 'A'. Obtenga alguna línea AD que se encuentre entre estos puntos.
4. Iterate para todos los puntos que se encuentran entre B y AD (a partir de BA). Deténgase cuando se encuentren n puntos. Seleccione un subintervalo de direcciones desde B hasta los puntos n y luego después de n (si no hay ningún punto después de n, use BC). Si se pueden encontrar menos de n puntos, configure el rango actual para el vértice A como la mitad izquierda del rango actual y vaya al paso 3.
5. Igual que el paso 4, pero para el vértice C.
6. Si los subintervalos A, B, C se cruzan, elija cualquier punto desde allí y termine. De lo contrario, si A&B está más cerca de A, configure el rango actual para el vértice A como la mitad derecha del rango actual y vaya al paso 3. De lo contrario, configure el rango actual para el vértice A como la mitad izquierda del rango actual y vaya al paso 3.

Complejidad: clasificación O(n * log n), búsqueda O(n * log n). (Combinación de búsqueda binaria y lineal).

Answer 4

Creo que hay un algoritmo de tiempo lineal. Vea el último párrafo del artículo "Iluminación por reflectores- por Steiger y Streinu". Su algoritmo funciona para cualquier k1, k2, k3 que se suman a n. Por lo tanto, k1 = k2 = k3 = n/3 es un caso especial.

Aquí está el enlace donde puede encontrar el artículo. http://www.sciencedirect.com/science/article/pii/S0925772197000278 un enlace de CiteSeerX es http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.4634