Voronoi pole

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

Definition

Let $V_p$ be the Voronoi cell of the site $p\in P$. If $V_p$ is bounded then its positive pole is the Voronoi vertex in $V_p$ with maximal distance to the sample point $p$. Furthermore, let $\bar{u}$ be the vector from $p$ to the positive pole. If the cell is unbounded, then a positive pole is not defined, and $\bar{u}$ is defined to be a vector in the average direction of all unbounded Voronoi edges of the cell.

The negative pole is the Voronoi vertex $v$ in $V_p$ with the largest distance to $p$ such that the vector $\bar{u}$ and the vector from $p$ to $v$ make an angle larger than $\frac{\pi}{2}$.

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.

References

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