- Title
- Fitting Voronoi diagrams to planar tesselations
- Creator
- Aloupis, Greg; Pérez-Rosés, Hebert; Pineda-Villavicencio, Guillermo; Taslakian, Perouz; Trinchet-Almaguer, Dannier
- Date
- 2013
- Type
- Text; Conference paper
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/62674
- Identifier
- vital:5733
- Identifier
- ISBN:03029743 (ISSN); 9783642452772 (ISBN)
- Abstract
- 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. © 2013 Springer-Verlag.
- Publisher
- Rouen, France Springer-Verlag
- Relation
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 8288 LNCS, p. 349-361
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- Dirichlet tesselation; Inverse Voronoi problem; Planar tesselation; Voronoi diagram
- Full Text
- Reviewed
- Hits: 1349
- Visitors: 1515
- Downloads: 205
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Accepted Version | 397 KB | Adobe Acrobat PDF | View Details Download |