Voronoi pole

In computational geometry, the positive and negative Voronoi poles of a cell in a Voronoi diagram are certain vertices of the diagram, chosen in pairs in each cell of the diagram to be far from the site generating that pair. They have applications in surface reconstruction.

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.^[1]

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 ${\tfrac {\pi }{2}}$ .^[1]

History and application

The poles were introduced in 1998 in two papers by Nina Amenta, Marshall Bern, and Manolis Kellis, for the problem of surface reconstruction. As they showed, any smooth surface that is sampled with sampling density inversely proportional to its curvature can be accurately reconstructed, by constructing the Delaunay triangulation of the combined set of sample points and their poles, and then removing certain triangles that are nearly parallel to the line segments between pairs of nearby poles.^[2]^[3]

References

^ ^a ^b Boissonnat, Jean-Daniel (2007). Effective Computational Geometry for Curves and Surfaces. Berlin: Springer. ISBN 978-3-540-33258-9.
^ Amenta, Nina; Bern, Marshall W. (1998). "Surface reconstruction by Voronoi filtering". In Janardan, Ravi (ed.). Proceedings of the Fourteenth Annual Symposium on Computational Geometry, Minneapolis, Minnesota, USA, June 7–10, 1998. ACM. pp. 39–48. doi:10.1145/276884.276889.
^ Amenta, Nina; Bern, Marshall W.; Kamvysselis, Manolis (1998). "A New Voronoi-based surface reconstruction algorithm". In Cunningham, Steve; Bransford, Walt; Cohen, Michael F. (eds.). Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1998, Orlando, FL, USA, July 19–24, 1998. ACM. pp. 415–421. doi:10.1145/280814.280947.

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

[ab-2] Amenta, Nina; Bern, Marshall W. (1998). "Surface reconstruction by Voronoi filtering". In Janardan, Ravi (ed.). Proceedings of the Fourteenth Annual Symposium on Computational Geometry, Minneapolis, Minnesota, USA, June 7–10, 1998. ACM. pp. 39–48. doi:10.1145/276884.276889.

[abk-3] Amenta, Nina; Bern, Marshall W.; Kamvysselis, Manolis (1998). "A New Voronoi-based surface reconstruction algorithm". In Cunningham, Steve; Bransford, Walt; Cohen, Michael F. (eds.). Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1998, Orlando, FL, USA, July 19–24, 1998. ACM. pp. 415–421. doi:10.1145/280814.280947.

[1]

[2]

[3]