# Fitting voronoi diagrams to planar tesselations

Greg Aloupis,
Hebert Pérez-Rosés,
Guillermo Pineda-Villavicencio,
Perouz Taslakian,
Dannier Trinchet-Almaguer

January 2013

### 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$ łq fitsq̊ $G$. This is the Generalized Inverse Voronoi Problem (GIVP). 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.

Publication

*International Workshop on Combinatorial Algorithms*