Polo Voronoi

En geometría computacional , los polos de Voronoi positivos y negativos de una celda en un diagrama de Voronoi son ciertos vértices del diagrama, elegidos en pares en cada celda del diagrama para que estén lejos del sitio que genera ese par. Tienen aplicaciones en la reconstrucción de superficies .

Definición

Ejemplo
Aquí x es el polo positivo de V _{p e} y es el negativo. Como la celda correspondiente a q no tiene límites, solo existe el polo negativo z .

Sea el diagrama de Voronoi para un conjunto de sitios , y sea la celda de Voronoi de correspondiente a un sitio . Si está acotada, entonces su polo positivo es el vértice del límite de que tiene la distancia máxima al punto . Si la celda no está acotada, entonces no se define un polo positivo. ^[1] ${\displaystyle V}$ ${\displaystyle P}$ ${\displaystyle V_{p}}$ ${\displaystyle V}$ ${\displaystyle p\in P}$ ${\displaystyle V_{p}}$ ${\displaystyle V_{p}}$ ${\displaystyle p}$

Además, sea el vector de a al polo positivo o, si la celda no tiene límites, sea un vector en la dirección promedio de todos los bordes de Voronoi no acotados de la celda. El polo negativo es entonces el vértice de Voronoi en con la mayor distancia a tal que el vector y el vector de a forman un ángulo mayor que . ^[1] ${\displaystyle {\bar {u}}}$ ${\displaystyle p}$ ${\displaystyle {\bar {u}}}$ ${\displaystyle v}$ ${\displaystyle V_{p}}$ ${\displaystyle p}$ ${\displaystyle {\bar {u}}}$ ${\displaystyle p}$ ${\displaystyle v}$ ${\displaystyle {\tfrac {\pi }{2}}}$

Historia y aplicación

Los polos fueron introducidos en 1998 en dos artículos de Nina Amenta , Marshall Bern y Manolis Kellis para el problema de reconstrucción de superficies . Como demostraron, cualquier superficie lisa que se muestrea con una densidad de muestreo inversamente proporcional a su curvatura se puede reconstruir con precisión, construyendo la triangulación de Delaunay del conjunto combinado de puntos de muestra y sus polos, y luego eliminando ciertos triángulos que son casi paralelos a los segmentos de línea entre pares de polos cercanos. ^{[2] [3]}

Referencias

1. Boissonnat, Jean-Daniel (2007). Geometría computacional efectiva para curvas y superficies . Berlín: Springer . ISBN 978-3-540-33258-9.
2. Amenta, Nina ; Bern, Marshall W. (1998). "Reconstrucción de superficies mediante filtrado de Voronoi". En Janardan, Ravi (ed.). Actas del Decimocuarto Simposio Anual sobre Geometría Computacional, Minneapolis, Minnesota, EE. UU., 7-10 de junio de 1998 . ACM. págs. 39-48. doi :10.1145/276884.276889.
3. Amenta, Nina ; Bern, Marshall W.; Kamvysselis, Manolis (1998). "Un nuevo algoritmo de reconstrucción de superficies basado en Voronoi". En Cunningham, Steve; Bransford, Walt; Cohen, Michael F. (eds.). Actas de la 25.ª Conferencia Anual sobre Gráficos por Computadora y Técnicas Interactivas, SIGGRAPH 1998, Orlando, FL, EE. UU., 19-24 de julio de 1998. ACM. págs. 415-421. doi :10.1145/280814.280947.