Prueba de diagramas de Voronoi

Question

Estoy teniendo un problema con esta prueba sobre diagramas de voronoi:

Demostrar que $V(p_i)$ (es decir, la célula de $\operatorname{Vor}(P)$ que corresponde a $p_i$) es ilimitada si y solamente si es convexa del punto set, $p_i$ $P = \{p_1,p_2,\ldots,p_n\}$.

¿Alguien puede ofrecer alguna ayuda?

Answer 1

Tomar un apoyo a la línea de $s$ $\text{conv}(P)$ corriendo a través de las $p_i$. A continuación, considere el rayo $r$ emanan de $p_i$ que es ortogonal a $s$ y se aleja de los $\text{conv}(P)$. Cada punto de $x$ en este rayo ha $p_i$ como punto más cercano de $P$. Para ver esto consideremos el círculo en torno a $x$ que toca a $p_i$, este círculo es tangente a $s$ y por lo tanto se cruza con $\text{conv}(P)$$p_i$.

Desde $r$ es ilimitado y que figuran en el $V(p_i)$, $V(p_i)$ es ilimitado.

Answer 2

Sugiero que le permite aprovechar la correspondiente triangulación de Delaunay para su prueba. Cada triángulo de la triangulación de Delaunay corresponde a un vértice de su Voronoi de las células. Puntos en el convex hull son exactamente los puntos que no están rodeados por triángulos de Delaunay. Más precisamente, un punto se encuentra en el casco convexo iff cada $\varepsilon$ barrio contiene los puntos que no pertenecen a ninguna de Delaunay triángulo. Lo que significa que hay direcciones en las que la célula se extiende infinitamente.