Voronoi pole

In geometry, the positive and negative Voronoi poles of a cell in a Voronoi diagram are certain vertices of the diagram.

Definition

Example
Here x is the positive pole of V_p and y its negative. As the cell corresponding to q is unbounded, only the negative pole z exists.

Let $V$ be the Voronoi diagram for a set of sites $P$, and let $V_p$ be the Voronoi cell of $V$ corresponding to a site $p\in P$. If $V_p$ is bounded, then its positive pole is the vertex of the boundary of $V_p$ that has maximal distance to the point $p$. If the cell is unbounded, then a positive pole is not defined.

Furthermore, let $\overline{u}$ be the vector from $p$ to the positive pole, or, if the cell is unbounded, let $\overline{u}$ be a vector in the average direction of all unbounded Voronoi edges of the cell. The negative pole is then the Voronoi vertex $v$ in $V_p$ with the largest distance to $p$ such that the vector $\overline{u}$ and the vector from $p$ to $v$ make an angle larger than $\frac{\pi }{2}$.

References

• Boissonnat, Jean-Daniel (2007). Effective Computational Geometry for Curves and Surfaces. Berlin: Springer. ISBN 978-3-540-33258-9.