## 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.

**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,

Web Site / Paper (pdf) / BibTeX

*In Proc. of the 9th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)*, June 2012, (invited)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