Maximizando el número de triángulos anidados

7

Hay un conjunto finito de puntos en un plano (aproximadamente 1500 puntos en la tarea actual). Necesito construir triángulos en esos puntos, ya que cada triángulo se encuentra completamente dentro de un triángulo más grande:

Ahoraquierounalgoritmoparamaximizarelnúmerodetalestriángulos.¿Dóndepuedoempezar?

Creoqueunadelasformasseríaelegirun"centro" y encontrar tres direcciones desde este centro con la mayoría de la densidad de puntos cerca de esas direcciones. O simplemente elija un triángulo central arbitrario manualmente y luego elija iterativamente un triángulo más grande con el menor área o la menor distancia.

    
pregunta wRAR 20.01.2014 - 09:31

3 respuestas

6

Primero, crea una lista de todos los triángulos (subconjuntos de 3 puntos). Luego haces una comparación por pares de cada uno de los dos triángulos T_i y T_j: o T_i está dentro de T_j, T_j está dentro de T_i o ninguna de las dos está dentro de la otra.

Interprete esto como un gráfico acíclico dirigido : los triángulos son los vértices del gráfico, y cada relación "T_i está dentro de T_j" define un borde dirigido de T_i a T_j. Ahora, encontrar la secuencia máxima de triángulos es solo el problema de la ruta más larga para este tipo de gráficos. Y como puede leer en el artículo de Wikipedia, existen algoritmos de tiempo lineal para resolver este problema.

"Tiempo lineal" aquí significa "lineal al número de bordes" (el número de pares de triángulos donde uno está dentro del otro). Para n puntos, hay que considerar

t := C(n,3)=n*(n-1)*(n-2)/6

triángulos (consulte coeficiente binomial ), y por lo tanto un máximo de

C(t,2) = t*(t-1)/2 

pares de triángulos, que pueden ser un número enorme al aumentar n: es un polinomio de orden O (n ^ 6). Pero como no se espera que la mayoría de los pares de triángulos sean del tipo "donde uno está dentro del otro", yo esperaría que el esfuerzo computacional del mundo real sea mucho menor. Para n debajo de 100, no debería ser un problema encontrar una solución directamente.

Para n > = 1.000, este enfoque probablemente no será lo suficientemente rápido para darle un resultado en un tiempo razonable. Por lo tanto, es mejor tratar de resolverlo con un algoritmo aproximado como el sugerido por @KonradMorawski, o (más fácil de implementar) recocido simulado . El "recocido simulado" necesitará un paso de "pequeña modificación", que puede implementarse eliminando uno o dos triángulos elegidos al azar de su "solución actual", y luego agregar triángulos nuevamente por algún tipo de "algoritmo codicioso" con un poco de aleatoriedad Seguramente necesitará experimentar con estos detalles para ver qué funciona mejor para su problema específico. Como recurso gratuito sobre estos temas, aquí encuentra un libro electrónico sobre diferentes técnicas de optimización global.

    
respondido por el Doc Brown 20.01.2014 - 13:43
4

Si está de acuerdo con una solución aproximada (no necesariamente la mejor posible), podría intentar un enfoque genético.

Encuentre una solución regular como punto de partida, usando un algoritmo simple como el sugerido por @Carra, luego haga, digamos, 1000 copias de esta solución inicial y continúe mutándolas al azar. Cambiando puntos, intentando agregar más triángulos, etc.

Recompense la mejor muestra y deseche las copias deficientes, por ejemplo. después de cada generación, se podría sobrescribir todo el conjunto genético con clones del mejor 5%. Para obtener mejores resultados, disminuya la temperatura con el tiempo; esto significa usar una mutación agresiva al principio, pero una tasa de mutación más lenta hacia el final para ajustar los resultados una vez que alcancen un nivel de alta calidad.

Después de algunas iteraciones, deberías terminar con una solución bastante buena.

    
respondido por el Konrad Morawski 20.01.2014 - 11:53
0

Mi intuición me dice que este es un problema NP-completo. Puedes intentar encontrar una buena solución pero no la mejor.

Entonces, sí, un comienzo sería escoger tres puntos en el medio, comenzar allí y crear un triángulo. Encuentre los puntos más cercanos a cada uno de estos tres puntos e intente crear un nuevo rectángulo. Debería dar una solución decente en la mayoría de los casos.

Para mejorar esto, puedes ejecutarlo varias veces con una cantidad de triángulos iniciales diferentes. O agregar algo de aleatoriedad a la toma de los puntos más cercanos. Ejecútelo varias veces y conserve la mejor solución que haya encontrado.

    
respondido por el Carra 20.01.2014 - 10:36

Lea otras preguntas en las etiquetas