Voronoi Diagram
Chee Yap and Vikram Sharma and Jyh-Ming Lien
Voronoi diagrams are extremely versatile as a data structure for many geometric applications. Computing this diagram “exactly”, in particularly for a polyhedral set in 3-D, has been an unrealized quest of computational geometers for over two decades.
2D Voronoi Diagram
Overview
Here, we show an implementation of an alternative approach based on the well-known Subdivision Paradigm. Our unique emphasis is the use of purely numerical primitives. We avoid exact (algebraic) primitives because- they are hard to implement correctly, and
- they fail to take full advantage of the resolution-limited properties of subdivision.
Publications
Towards Exact Numerical Voronoi Diagrams, Chee K. Yap and Vikram Sharma and Jyh-Ming Lien, In Proc. of the 9th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), June 2012, (invited)
Web Site / Paper (pdf) / BibTeX
Web Site / Paper (pdf) / BibTeX
Software
- Software will be released soon.
Examples
A simple 2D example. The voronoi vertex is approximated as the center of the box containing it.
Same example, with finer subdivision.

This figure shows three line bisectors (in purple), one point bisector (in green) and two parabolas (in grey)
created by the features associated with the highlighted box (with red boundary).

A slightly more complex example

A polygone with hole. In this example, a Voronoi curve is created by connecting the mid points
of two box edges.

Related Work/Links
List of MASC Research Pages