En geometría computacional , un diagrama de potencia , también llamado diagrama de Laguerre-Voronoi , complejo de células de Dirichlet , teselación radical de Voronoi o teselación seccional de Dirichlet , es una partición del plano euclidiano en celdas poligonales definidas a partir de un conjunto de círculos. La celda para un círculo dado C consta de todos los puntos para los cuales la distancia en potencia a C es menor que la distancia en 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]
Si C es un círculo y P es un punto exterior a C , entonces la potencia de P con respecto a C es el cuadrado de la longitud de un segmento de recta desde P hasta 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 se puede extender a todos los puntos del 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 potencia de un conjunto de n círculos Ci es una partición del plano en n regiones Ri (llamadas celdas), de modo que un punto P pertenece a Ri siempre que el círculo Ci sea el círculo que minimiza la potencia de P. [2] [3] [4]
En el caso n = 2, el diagrama de potencia consta de dos semiplanos , separados por una línea llamada eje radical o cordal de los dos círculos. A lo largo del eje radical, ambos círculos tienen el mismo poder. De manera más general, en cualquier diagrama de potencia, cada celda Ri es un polígono convexo , la intersección de los semiespacios delimitados por los ejes radicales del círculo Ci entre sí. Las tripletas de celdas se encuentran en los vértices del diagrama, que son los centros radicales de los tres círculos cuyas celdas se encuentran en el vértice. [2] [3] [4]
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. 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 compararla con las distancias a los otros sitios, y el diagrama de Voronoi ponderado multiplicativamente, en el que el peso de un El 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 el centro de cada 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 del círculo sean iguales, esta resta no influye en la comparación y el diagrama de potencia coincide con el diagrama de Voronoi. [3] [4]
Un diagrama de potencia plano también puede interpretarse como una sección transversal plana de un diagrama de Voronoi tridimensional no ponderado. En esta interpretación, el conjunto de centros de círculos en el plano de sección transversal son las proyecciones perpendiculares de los sitios tridimensionales de Voronoi, y el radio al cuadrado de cada círculo es una constante K menos la distancia al cuadrado del sitio correspondiente desde la sección transversal. plano de sección, donde K se elige lo suficientemente grande como para 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]
Se pueden construir diagramas de potencia bidimensionales 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 semiespacios 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] También se utiliza para resolver el problema de transporte óptimo semidiscreto [8] que a su vez tiene numerosas aplicaciones, como la reconstrucción temprana del universo [9] o la dinámica de fluidos. [10]
Aurenhammer (1987) remonta la definición de 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 puede iluminarse desde como máximo 2 n fuentes de luz puntuales. [11] Los diagramas de potencia han aparecido en la literatura con otros nombres, incluido el "diagrama de Laguerre-Voronoi", "complejo de células de Dirichlet", "teselación radical de Voronoi" y "teselación seccional de Dirichlet". [12]
