- Title
- Fitting Voronoi diagrams to planar tesselations
- Creator
- Aloupis, Greg; Pérez-Rosés, Hebert; Pineda-Villavicencio, Guillermo; Taslakian, Perouz; Trinchet-Almaguer, Dannier
- Relation
- 24th International Workshop on Combinatorial Algorithms (IWOCA 2013). Combinatorial Algorithms: 24th International Workshop (IWOCA 2013) (Rouen, France 10-12 July, 2013) p. 349-361
- Publisher Link
- http://dx.doi.org/10.1007/978-3-642-45278-9_30
- Publisher
- Springer
- Resource Type
- conference paper
- Date
- 2013
- Description
- 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.
- Subject
- Voronoi diagram; Dirichlet tesselation; planar tesselation; inverse Voronoi problem
- Identifier
- http://hdl.handle.net/1959.13/1341045
- Identifier
- uon:28645
- Identifier
- ISBN:9783642452772
- Language
- eng
- Reviewed
- Hits: 3280
- Visitors: 3207
- Downloads: 0