algorithm language-agnostic computational-geometry

algorithm - Partición triángulo



language-agnostic computational-geometry (4)

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

Entrada:

  • Coordenadas de un triángulo delimitador: (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 puntos 3n : (x_i,y_i) para i=1...3n

Salida:

  • Un punto (sx,sy) que divide el triángulo en 3 subtriángulos de modo que cada subtriángulo contenga 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 garantizado que existe tal punto. Cualquier punto será suficiente (la respuesta no es necesariamente única).

Aquí hay un ejemplo del problema para n=2 (6 puntos). Nos dan las coordenadas de cada uno de los puntos de color y las coordenadas de cada vértice del triángulo grande. El punto de división está rodeado por un círculo gris.

¿Alguien puede sugerir un algoritmo más rápido que O(n^2) ?

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 colocamos el punto central C 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 (perturbando C y hayamos terminado) o CP llegue a un punto. En este último caso, deslice C lejos de P hasta que el triángulo CRP ya no sea deficiente (hemos terminado) o CQ llegue a un punto, en cuyo caso comenzamos a deslizar C hacia Q nuevamente.

Claramente, la implementación no puede "deslizar" los puntos, por lo que para cada triángulo que implica C , para cada vértice S de ese triángulo que no sea C , almacene los puntos dentro del triángulo en un árbol de búsqueda binario ordenado 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 punto-línea y puede manejarse en el tiempo O(log n) . Los ángulos PC y QC y RC son todos monotónicos, por lo que cada una de las líneas O(1) llega a cada punto como máximo una vez.

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

Cada paso comienza con un punto inicial, el cual divide el triángulo en triángulos. Si cada uno tiene n puntos, estamos terminados. Si no, considere el sub-triángulo que está más alejado de la n deseada. Supongamos que tiene demasiados, solo por ahora. Los desequilibrios se suman a cero, por lo que al menos uno de los otros dos sub-triángulos tiene muy pocos puntos. El tercer sub-triángulo también tiene muy pocos puntos, 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 desequilibrado y considere mover el punto central a lo largo de la línea que se aleja de él. Mientras lo hace, se reducirá el desequilibrio del punto más desequilibrado. Para cada punto en el triángulo, puede calcular cuándo ese punto se cruza hacia dentro o hacia afuera del subtriángulo más desequilibrado a medida que mueve el punto central. Por lo tanto, puede trabajar en el tiempo n donde mover el punto central para dar al triángulo más desequilibrado cualquier conteo deseado.

A medida que mueva el punto central, puede elegir si los puntos se mueven hacia fuera desde el sub-triángulo más desequilibrado, pero no puede elegir a cuál de los otros dos sub-triángulos van, o desde - pero puede predecir cuál de qué lado. la línea a lo largo de la cual desliza el punto central en el 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 sub-triángulo que estaba exactamente equilibrado. Sin embargo, si el sub-triángulo desequilibrado tiene n + k puntos, al mover k / 2 de ellos, puede moverse, en el peor de los casos, al caso en que él y el sub-triángulo previamente balanceado están fuera de k / 2. El tercer triángulo puede estar desequilibrado por hasta k, en la otra dirección, pero en este caso una segunda pasada reducirá el desequilibrio máximo a algo por debajo de k / 2.

Por lo tanto, en el caso de un gran desequilibrio, podemos reducirlo en el peor de los casos como 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 estemos en casos especiales en los que nos preocupamos. sobre 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 suma constante.

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

  1. Ordena los puntos según la dirección del vértice A Clasifíquelos para B y C también.
  2. Establezca el rango actual para que el vértice A sea ​​todos los puntos.
  3. Seleccione 2 puntos medios del rango para el vértice A Estos 2 puntos definen el subrango para ''A''. Obtener una línea AD encuentra entre estos puntos.
  4. Iterar para todos los puntos que se encuentran entre B y AD (a partir de BA ). Pare cuando n puntos encontrados. Seleccione el subrango de direcciones de B a los puntos n siguiente 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 que el vértice A sea ​​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 subrangos A , B , C intersecan, elija cualquier punto desde allí y finalice. De lo contrario, si A&B está más cerca de A , configure el rango actual para que el vértice A sea ​​la mitad derecha del rango actual y vaya al paso 3. De lo contrario, establezca el rango actual para que el vértice A sea ​​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).