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$ 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 ${\bar {u}}$ be the vector from $p$ to the positive pole, or, if the cell is unbounded, let ${\bar {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 ${\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.