Geodesic Voronoi Diagrams with Polyline Generators
Loading...
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
Geodesic Voronoi diagrams (GVDs) defined on triangle meshes with polyline generators are studied in this paper.
We introduce a new concept, called local Voronoi diagram, or LVD, which is a weighted Euclidean Voronoi diagram
on a mesh triangle. We show that when restricting on a mesh triangle, the GVD is a subset of the LVD, which
can be computed by using the existing 2D techniques. Moreover, only two types of mesh faces can contain GVD
edges. Guided by our theoretical findings, the geodesic Voronoi diagram with polyline generators can be built in
O(nN logN) time and takes O(nN) space on an n-face mesh with m generators, where N = maxfm;ng.
Description
@inproceedings{:10.2312/sgp20141380,
booktitle = {Symposium on Geometry Processing 2014 - Posters},
editor = {Thomas Funkhouser and Shi-Min Hu},
title = {{Geodesic Voronoi Diagrams with Polyline Generators}},
author = {Chunxu Xu and Yong-Jin Liu and Qian Sun and Jinyan Li and Ying He},
year = {2014},
publisher = {The Eurographics Association},
ISSN = {-},
ISBN = {-},
DOI = {/10.2312/sgp20141380}
}