Given a tesselation of the plane, defined by a planar straight-line graph G, we want to find a minimal set S of points in the plane, such that the Voronoi diagram associated with S 'fits' G. This is the Generalized Inverse Voronoi Problem (GIVP), defined in [12] and rediscovered recently in [3]. Here we give an algorithm that solves this problem with a number of points that is linear in the size of G, assuming that the smallest angle in G is constant.
History
Volume
8288
Pagination
349-361
Location
Rouen, France
Start date
2013-07-10
End date
2013-07-12
ISSN
0302-9743
eISSN
1611-3349
ISBN-13
9783642452772
Language
eng
Publication classification
E1.1 Full written paper - refereed
Copyright notice
2013, Springer-Verlag Berlin Heidelberg
Editor/Contributor(s)
Lecroq T, Mouchard L
Title of proceedings
IWOCA 2013 : Proceedings of the 24th International Workshop on Combinatorial Algorithms 2013