En geometría computacional , un diagrama de potencia , también llamado diagrama de Laguerre-Voronoi , complejo de células de Dirichlet , teselación de Voronoi radical o teselación de Dirichlet seccional , es una partición del plano euclidiano en celdas poligonales definidas a partir de un conjunto de círculos. La celda de un círculo C dado consta de todos los puntos para los cuales la distancia de potencia a C es menor que la distancia de potencia a los otros círculos. El diagrama de potencia es una forma de diagrama de Voronoi generalizado, y coincide con el diagrama de Voronoi de los centros de los círculos en el caso de que todos los círculos tengan radios iguales. [1] [2] [3] [4]
Definición
Si C es un círculo y P es un punto fuera de C , entonces la potencia de P con respecto a C es el cuadrado de la longitud de un segmento de línea de P a un punto T de tangencia con C . De manera equivalente, si P tiene una distancia d desde el centro del círculo, y el círculo tiene un radio r , entonces (según el teorema de Pitágoras ) la potencia es d 2 - r 2 . La misma fórmula d 2 - r 2 puede extenderse a todos los puntos en el plano, independientemente de si están dentro o fuera de C : los puntos en C tienen potencia cero y los puntos dentro de C tienen potencia negativa. [2] [3] [4]
El diagrama de energía de un conjunto de n círculos C i es una partición del plano en n regiones R i (llamadas células), de manera que un punto P pertenece a R i siempre círculo C i es el círculo minimizar la potencia de P . [2] [3] [4]
En el caso n = 2, el diagrama de energía consiste en dos semiplanos , separadas por una línea llamada el eje radical o chordale de los dos círculos. A lo largo del eje radical, ambos círculos tienen el mismo poder. Más en general, en cualquier diagrama de potencia, cada célula R i es un polígono convexo , la intersección de los semiespacios delimitadas por los ejes radicales de círculo C i uno con el otro círculo. Los triples de células se encuentran en los vértices del diagrama, que son los centros radicales de los tres círculos cuyas células se encuentran en el vértice. [2] [3] [4]
Construcciones relacionadas
El diagrama de potencia puede verse como una forma ponderada del diagrama de Voronoi de un conjunto de sitios puntuales, una partición del plano en celdas dentro de las cuales uno de los sitios está más cerca que todos los demás sitios. Otras formas de diagrama de Voronoi ponderado incluyen el diagrama de Voronoi ponderado aditivamente, en el que cada sitio tiene un peso que se suma a su distancia antes de compararlo con las distancias a los otros sitios, y el diagrama de Voronoi ponderado multiplicativamente, en el que el peso de un sitio se multiplica por su distancia antes de compararlo con las distancias a los otros sitios. Por el contrario, en el diagrama de potencia, podemos ver cada centro del círculo como un sitio y el radio al cuadrado de cada círculo como un peso que se resta de la distancia euclidiana al cuadrado antes de compararlo con otras distancias al cuadrado. En el caso de que todos los radios de los círculos sean iguales, esta resta no hace ninguna diferencia en la comparación y el diagrama de potencia coincide con el diagrama de Voronoi. [3] [4]
Un diagrama de potencia plano también se puede interpretar como una sección transversal plana de un diagrama de Voronoi tridimensional no ponderado. En esta interpretación, el conjunto de centros circulares en el plano de la sección transversal son las proyecciones perpendiculares de los sitios de Voronoi tridimensionales, y el radio al cuadrado de cada círculo es una constante K menos la distancia al cuadrado del sitio correspondiente desde la intersección. plano de sección, donde K se elige lo suficientemente grande para hacer que todos estos radios sean positivos. [5]
Al igual que el diagrama de Voronoi, el diagrama de potencia se puede generalizar a espacios euclidianos de cualquier dimensión. El diagrama de potencia de n esferas en d dimensiones es combinatoriamente equivalente a la intersección de un conjunto de n semiespacios orientados hacia arriba en d + 1 dimensiones, y viceversa. [3]
Algoritmos y aplicaciones
Los diagramas de potencia bidimensionales pueden construirse mediante un algoritmo que se ejecuta en el tiempo O ( n log n ). [2] [3] De manera más general, debido a la equivalencia con las intersecciones de semiespacio de dimensiones superiores, los diagramas de potencia d- dimensionales (para d > 2) pueden construirse mediante un algoritmo que se ejecuta en el tiempo. [3]
El diagrama de potencia se puede utilizar como parte de un algoritmo eficiente para calcular el volumen de una unión de esferas. La intersección de cada esfera con su celda del diagrama de potencia da su contribución a la unión total, a partir de la cual se puede calcular el volumen en el tiempo proporcional a la complejidad del diagrama de potencia. [6]
Otras aplicaciones de los diagramas de potencia incluyen estructuras de datos para probar si un punto pertenece a una unión de discos, [2] algoritmos para construir el límite de una unión de discos, [2] y algoritmos para encontrar las dos bolas más cercanas en un conjunto de bolas. . [7]
Historia
Aurenhammer (1987) remonta la definición de la distancia de poder al trabajo de los matemáticos del siglo XIX Edmond Laguerre y Georgy Voronoy . [3] Fejes Tóth (1977) definió diagramas de potencia y los utilizó para mostrar que el límite de una unión de n discos circulares siempre se puede iluminar desde un máximo de 2 n fuentes de luz puntuales. [8] Los diagramas de potencia han aparecido en la literatura bajo otros nombres, incluyendo "diagrama de Laguerre-Voronoi", "complejo de células de Dirichlet", "teselación de Voronoi radical" y "teselación de Dirichlet seccional". [9]
Referencias
- ↑ Linhart, J. (1981), "Dirichletsche Zellenkomplexe mit maximaler Eckenzahl", Geometriae Dedicata , 11 (3): 363–367, doi : 10.1007 / BF00149360 , MR 0627538.
- ^ a b c d e f g Imai, Hiroshi; Iri, Masao; Murota, Kazuo (1985), "Diagrama de Voronoĭ en la geometría de Laguerre y sus aplicaciones", SIAM Journal on Computing , 14 (1): 93-105, doi : 10.1137 / 0214006 , MR 0774929.
- ^ a b c d e f g h yo Aurenhammer, F. (1987), "Diagramas de potencia: propiedades, algoritmos y aplicaciones", SIAM Journal on Computing , 16 (1): 78–96, doi : 10.1137 / 0216006 , MR 0873251.
- ^ a b c d e Edelsbrunner, Herbert (1987), "13.6 Diagramas de potencia", Algoritmos en geometría combinatoria , EATCS Monographs on Theoretical Computer Science, 10 , Springer-Verlag, págs. 327–328.
- ^ Ash, Peter F .; Bolker, Ethan D. (1986), "Teselaciones de Dirichlet generalizadas", Geometriae Dedicata , 20 (2): 209–243, doi : 10.1007 / BF00164401 , MR 0833848.
- ^ Avis, David ; Bhattacharya, Binay K .; Imai, Hiroshi (1988), "Calculando el volumen de la unión de esferas" (PDF) , The Visual Computer , 3 (6): 323–328, doi : 10.1007 / BF01901190.
- ^ Guibas, Leonidas ; Zhang, Li (1998), "Diagramas de potencia y proximidad euclidianos", Décima Conferencia Canadiense de Geometría Computacional.
- ^ Fejes Tóth, L. (1977), "Iluminación de discos convexos", Acta Mathematica Academiae Scientiarum Hungaricae , 29 (3–4): 355–360, doi : 10.1007 / BF01895856 , MR 0464065.
- ^ Aurenhammer, F .; Imai, H. (1988), "Relaciones geométricas entre diagramas de Voronoĭ", Geometriae Dedicata , 27 (1): 65–75, doi : 10.1007 / BF00181613 , MR 0950323.