Aprendiendo triángulos en el plano

13

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).mR2±1TT

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?O(m6)m

Aria
fuente
Para ser claros: los vértices del triángulo no necesitan ser puntos de la colección, ¿verdad? ¿Y es aceptable tener puntos negativos en el límite?
ex0du5
(1) Había votado para cerrar la pregunta porque había entendido mal el problema. El sistema no me permite cancelar mi voto, pero prácticamente lo cancelo. (2) Creo que hay un algoritmo de tiempo O (m log m), pero no tengo tiempo para verificarlo en este momento. La idea es calcular el casco convexo de los ejemplos positivos y barrer alrededor de este casco convexo para encontrar tres líneas que formen el triángulo deseado.
Tsuyoshi Ito
@ ex0du5: de hecho, los vértices del triángulo no necesitan consistir en los puntos de muestra. En cuanto a los problemas de límites, estos pueden ignorarse aquí, ya que no son esenciales. [Si el límite cuenta como parte del triángulo, entonces no tendrá puntos negativos en el límite.]
Aryeh
@ TsuyoshiIto: Estaba pensando de manera similar, pero hay casos en los que no puede hacer que los bordes del triángulo sean colineales a los bordes del casco convexo, pero todavía existe un triángulo. El triángulo todavía obviamente contiene el casco convexo, pero no se trata solo de extender las líneas del casco y encontrar el triángulo. Es posible que necesite líneas que giran alrededor de algunos de los vértices para evitar los puntos negativos. Por eso pregunté sobre los negativos en el límite, para permitir un algoritmo de búsqueda que eligiera líneas desde los vértices del casco a negativos para mantener una búsqueda discreta.
ex0du5
@ ex0du5: Bueno, no asumí que los bordes del triángulo son paralelos a algunos bordes del casco convexo de los ejemplos positivos.
Tsuyoshi Ito

Respuestas:

14

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 FCqqCCW(q)CFW(q)CF. Tanto como F se pueden construir en tiempo O ( n log n ) .CFO(nlogn)

ejemplo de $ C $ y $ F $

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).FFO(n)Fee

Vea el documento original para más detalles:

Jeffε
fuente
3

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 ).TT

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).tABtBCBC

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

  1. Calcule los puntos de intersección de con todas las otras líneas;t
  2. Encuentre un extremo B (más alejado de ), el punto B y la línea correspondiente t ' a la derecha (o izquierda) de A , de modo que el ángulo del psuedotriangle A B C (= A B , B C y la parte del casco convexo entre A y C ) no contiene puntos '-1' (es decir, no contiene ningún punto).ABtAABCABBCAC
  3. Haga lo mismo con la línea y vea si podemos' cerrar 'el triángulo.t

Parece que esto sería un tiempo de ejecución de . ¿Quizás esto pueda mejorarse usando algunas estructuras de datos?O(m2)

Shalabuda
fuente