Planar Minimization Diagrams via Subdivision with Applications to Anisotropic Voronoi Diagrams

H. Bennett, E. Papadopoulou, C. Yap

Research output: Contribution to journalArticlepeer-review


Let X = {f1, …, fn} be a set of scalar functions of the form fi : ℝ2 → ℝ which satisfy some natural properties. We describe a subdivision algorithm for computing a clustered ε-isotopic approximation of the minimization diagram of X. By exploiting soft predicates and clustering of Voronoi vertices, our algorithm is the first that can handle arbitrary degeneracies in X, and allow scalar functions which are piecewise smooth, and not necessarily semi-algebraic. We apply these ideas to the computation of anisotropic Voronoi diagram of polygonal sets; this is a natural generalization of anisotropic Voronoi diagrams of point sites, which extends multiplicatively weighted Voronoi diagrams. We implement a prototype of our anisotropic algorithm and provide experimental results.

Original languageEnglish (US)
Pages (from-to)229-247
Number of pages19
JournalComputer Graphics Forum
Issue number5
StatePublished - Aug 1 2016


  • Categories and Subject Descriptors (according to ACM CCS)
  • F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems—Geometrical problems and computations
  • G.1.0 [Numerical Analysis]: General—Interval arithmetic
  • G.1.2 [Numerical Analysis]: Approximation—Approximation of surfaces and contours
  • G.4 [Mathematical Software]: —Algorithm design and analysis
  • I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Geometric algorithms

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Planar Minimization Diagrams via Subdivision with Applications to Anisotropic Voronoi Diagrams'. Together they form a unique fingerprint.

Cite this