Voronoi pole

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

{{ safesubst:#invoke:Unsubst||$N=Context |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} Given a point set and the corresponding Voronoi diagram, then for each cell at most two poles are defined, namely the positive and negative poles.

Definition

Let ${\displaystyle V_{p}}$ be the corresponding cell of the point ${\displaystyle p\in P}$. If ${\displaystyle V_{p}}$ is bounded then its positive pole is the Voronoi vertex in ${\displaystyle V_{p}}$ with maximal distance to the sample point ${\displaystyle p}$. Furthermore, let ${\displaystyle {\bar {u}}}$ be the vector from ${\displaystyle p}$ to the positive pole. If the cell is unbounded, then a positive pole is not defined, and ${\displaystyle {\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 ${\displaystyle v}$ in ${\displaystyle V_{p}}$ with the largest distance to ${\displaystyle p}$ such that the vector ${\displaystyle {\bar {u}}}$ and the vector from ${\displaystyle p}$ to ${\displaystyle v}$ make an angle larger than ${\displaystyle {\frac {\pi }{2}}}$.

Example

Here ${\displaystyle x}$ is the positive pole of ${\displaystyle V_{p}}$ and ${\displaystyle y}$ its negative. As the cell corresponding to ${\displaystyle q}$ is unbounded only the negative pole ${\displaystyle z}$ exists.

References

• {{#invoke:citation/CS1|citation

|CitationClass=book }}