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?
$\begingroup$
$\endgroup$
2
asked Dec 13, 2016 at 6:39
-
$\begingroup$ arxiv.org/abs/1308.5550, see references there $\endgroup$– Moritz FirschingCommented Dec 13, 2016 at 9:42
-
$\begingroup$ @MoritzFirsching that solves my problem! If you could turn that into an answer, I would accept it. $\endgroup$– Manfred WeisCommented Dec 13, 2016 at 9:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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
answered Dec 13, 2016 at 9:50
$\begingroup$
(Image from Stefan Huber.)
$\endgroup$
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.)
answered Sep 2, 2018 at 22:52