Asigné a mis alumnos el problema de encontrar un triángulo consistente con una colección de puntos en , etiquetado con . (Un triángulo es consistente con la muestra etiquetada si contiene todos los puntos positivos y ninguno de los negativos; por supuesto, la muestra admite al menos 1 triángulo consistente).
Lo mejor que podrían hacer (o yo) es un algoritmo que se ejecuta en el tiempo , donde es el tamaño de la muestra. ¿Alguien puede hacerlo mejor?
Respuestas:
Como sugiere @TsuyoshiIto, existe un algoritmo de tiempo para este problema, debido a Edelsbrunner y Preparata. De hecho, su algoritmo encuentra un polígono convexo con el mínimo número posible de aristas que separa los dos conjuntos de puntos. También prueban un límite inferior de Ω ( n log n ) para el problema más general en el modelo de árbol de decisión algebraico; Sin embargo, no está claro si este límite inferior se aplica a la caja del triángulo.O(nlogn) Ω(nlogn)
Una descripción completa del algoritmo es demasiado larga para publicar aquí, pero esta es la idea básica. Sea el casco convexo de los puntos positivos. Para cada punto negativo q , considere las líneas a través de q que son tangentes a C . Estas líneas dividen el plano en cuatro cuñas, una de las cuales contiene C ; dejó W ( q ) sea la cuña opuesta el uno que contiene C . Finalmente, sea F (la "región prohibida") la unión de todas las cuñas W ( q ) . Cualquier triángulo de separación debe separar C de FC q q C C W(q) C F W(q) C F . Tanto como F se pueden construir en tiempo O ( n log n ) .C F O(nlogn)
Etiquete los bordes de alternativamente en sentido horario y antihorario. Edelsbrunner y Preparata demuestran además que si existe un triángulo de separación, entonces hay un triángulo que separa cuyos bordes son colineales con los bordes en sentido horario del F . En O ( n ) tiempo adicional, podemos encontrar el borde (necesariamente en el sentido de las manecillas del reloj) de F golpeado por un rayo desde cada borde en el sentido de las manecillas del reloj e ; llama a esta ventaja el "sucesor" de e . Los punteros sucesores dividen los bordes en sentido horario en ciclos; Si hay un triángulo separador, uno de estos ciclos sucesores tiene una longitud de 3 (y ninguno tiene una longitud de más de 4).F F O(n) F e e
Vea el documento original para más detalles:
fuente
Me parece que es suficiente considerar las líneas tangentes de los puntos '-1' en el casco convexo de los puntos '+1' como candidatos para los lados de (digamos que los puntos '+1' serán internos a T ).T T
Lástima, no puedo publicar imágenes aquí. Pero imagine esto: es la línea tangente al casco convexo que pasa por algún punto '-1'. A es el punto de tangencia. B es el punto extremo (ver más abajo) en t , y B C es la línea tangente desde el punto B ( C es el punto de tangencia).t A B t BC B C
Entonces, el algoritmo es el siguiente. Para cada línea de las líneas de tangentes podemos intentar construir un triángulo basado en él:t
Parece que esto sería un tiempo de ejecución de . ¿Quizás esto pueda mejorarse usando algunas estructuras de datos?O(m2)
fuente