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
  1. they are hard to implement correctly, and
  2. they fail to take full advantage of the resolution-limited properties of subdivision.
We encapsulate our numerical approach using the concept of soft primitives that conservatively converge to the exact ones in the limit.

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

Software

Examples
A simple 2D example. The voronoi vertex is approximated as the center of the box containing it.
A simple example
Same example, with finer subdivision.
A simple example
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 simple example
A slightly more complex example
A simple example
A polygone with hole. In this example, a Voronoi curve is created by connecting the mid points
of two box edges.
A simple example

Related Work/Links

List of MASC Research Pages
Computer Science @ George Mason University