4
$\begingroup$

how can one construct a finite set of points in the euclidean plane from its Voronoi Diagram and, what is the complexity of the problem?

$\endgroup$
2
  • $\begingroup$ arxiv.org/abs/1308.5550, see references there $\endgroup$ – Moritz Firsching Dec 13 '16 at 9:42
  • $\begingroup$ @MoritzFirsching that solves my problem! If you could turn that into an answer, I would accept it. $\endgroup$ – Manfred Weis Dec 13 '16 at 9:46
5
$\begingroup$

This is a well studied problem and there are a couple of algorithms, for example using linear programming. For an overview take a recent reference, for example:

Fitting Voronoi Diagrams to Planar Tesselations by Greg Aloupis, Hebert Pérez-Rosés, Guillermo Pineda-Villavicencio, Perouz Taslakian, Dannier Trinchet

$\endgroup$
2
$\begingroup$

See also:

Biedl, Therese, Martin Held, and Stefan Huber. "Recognizing straight skeletons and Voronoi diagrams and reconstructing their input." In Voronoi Diagrams in Science and Engineering (ISVD), 2013 10th International Symposium on, pp. 37-46. IEEE, 2013. (IEEE link.)


         
          (Image from Stefan Huber.)


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.