Planar Minimization Diagrams via Subdivision with Applications to Anisotropic Voronoi Diagrams
Loading...
Date
2016
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and John Wiley & Sons Ltd.
Abstract
Let X = {f1, . . ., fn} be a set of scalar functions of the form fi : R2 →R which satisfy some natural properties. We describe a subdivision algorithm for computing a clustered e-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.
Description
@article{10.1111:cgf.12979,
journal = {Computer Graphics Forum},
title = {{Planar Minimization Diagrams via Subdivision with Applications to Anisotropic Voronoi Diagrams}},
author = {Bennett, Huck and Papadopoulou, Evanthia and Yap, Chee},
year = {2016},
publisher = {The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/cgf.12979}
}