Voronoi diagram computations for planar NURBS curves

Joon Kyung Seong, Elaine Cohen, Gershon Elber

Research output: Contribution to conferencePaperpeer-review

17 Citations (Scopus)


We present robust and efficient algorithms for computing Voronoi diagrams of planar freeform curves. Boundaries of the Voronoi diagram consist of portions of the bisector curves between pairs of planar curves. Our scheme is based on computing critical structures of the Voronoi diagrams, such as self-intersections and junction points of bisector curves. Since the geometric objects we consider in this paper are represented as freeform NURBS curves, we were able to reformulate the solution to the problem of computing those critical structures into the zero-set solutions of a system of nonlinear piecewise rational equations in parameter space. We present a new algorithm for computing error-bounded bisector curves using a distance surface constructed from error-bounded offset approximations of planar curves. This error-bounded algorithm is fast and produces bisector curves that are correct both in topology and geometry. Once bisectors are computed, both local and global self-intersections of the bisector curves are located and trimmed away by solving a system of three piecewise rational equations in three variables. Further, our method computes junction points at which three or more trimmed bisector curves intersect by transforming them into the solutions to a system of piecewise rational equations in the merged parameter space of the planar curves. The bisectors are trimmed at those self-intersection and global junction points. The Voronoi diagram is then computed from the trimmed bisectors using a pruning algorithm. We demonstrate the effectiveness of our approach with several experimental results.

Original languageEnglish
Number of pages12
Publication statusPublished - 2008
Externally publishedYes
Event2008 ACM Symposium on Solid and Physical Modeling 2008, SPM'08 - Stony Brook, NY, United States
Duration: 2008 Jun 22008 Jun 4


Other2008 ACM Symposium on Solid and Physical Modeling 2008, SPM'08
Country/TerritoryUnited States
CityStony Brook, NY


  • Bisectors
  • Freeform curves
  • Junction points
  • Problem reduction scheme
  • Self-intersections
  • Voronoi diagram
  • Zero-set

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design
  • Software


Dive into the research topics of 'Voronoi diagram computations for planar NURBS curves'. Together they form a unique fingerprint.

Cite this