Bitangente

Las cuatro bitangentes de dos polígonos convexos disjuntos pueden ser determinadas eficientemente mediante un algoritmo basado en búsqueda binaria en el que se mantiene un puntero de búsqueda binario en las listas de bordes de cada polígono y se mueve uno de los punteros a la izquierda o a la derecha en cada escalón de cálculo, dependiendo de donde las líneas tangentes a los bordes desde las posiciones de los dos punteros se cruzan entre sí. Este cálculo de bitangentes es una subrutina clave en estructuras de datos para mantener envolventes convexas dinámicamente (Overmars y van Leeuwen, 1981). (txt,) describen un algoritmo para enumerar eficientemente todos los segmentos de línea bitangentes que no cruzan ninguna de las otras curvas en un sistema de múltiples curvas convexas disjuntas, usando una técnica basada en pseudotriangulación.

Las bitangentes se pueden utilizar para acelerar el enfoque de grafos de visibilidad en la resolución del problema del camino mínimo Euclídeo: el recorrido más corto entre una colección de obstáculos poligonales puede entrar o salir del límite de un obstáculo por una de sus bitangentes, por lo que el camino más corto puede encontrarse aplicando el Algoritmo de Dijkstra a un subgrafo del gráfico de visibilidad formado por los bordes de visibilidad que se encuentran en las líneas bitangentes (Rohnert, 1986).

Una bitangente difiere de un recta secante en que una línea secante puede cruzar la curva en los dos puntos por donde la atraviesa. También se pueden considerar bitangentes que no son líneas rectas; por ejemplo, el conjunto simétrico de una curva es el lugar de los centros de los círculos que son tangentes a la curva en dos puntos.

Las bitangentes a un par de círculos figuran de manera destacada en la construcción ideada por Jakob Steiner en 1826 de los círculos de Malfatti; en el problema de la correa consistente en calcular la longitud de una correa de conexión entre dos poleas; y en el teorema de Casey sobre la caracterización de conjuntos de cuatro círculos con un círculo tangente común.

• Overmars, M. H.; van Leeuwen, J. (1981), «Maintenance of configurations in the plane», Journal of Computer and System Sciences 23 (2): 166-204, doi:10.1016/0022-0000(81)90012-X ..
• Pocchiola, Michel; Vegter, Gert (1996a), «The visibility complex», International Journal of Computational Geometry and Applications 6 (3): 297-308, doi:10.1142/S0218195996000204, Preliminary version in Ninth ACM Symposium on Computational Geometry (1993) 328–337]., archivado desde el original el 3 de diciembre de 2006, consultado el 4 de mayo de 2017 ..
• Pocchiola, Michel; Vegter, Gert (1996b), «Topologically sweeping visibility complexes via pseudotriangulations», Discrete and Computational Geometry 16 (4): 419-453, doi:10.1007/BF02712876 ..
• Rohnert, H. (1986), «Shortest paths in the plane with convex polygonal obstacles», Information Processing Letters 23 (2): 71-76, doi:10.1016/0020-0190(86)90045-1 ..