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$ 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
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érezRosés, Guillermo PinedaVillavicencio, Perouz Taslakian, Dannier Trinchet
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. 3746. IEEE, 2013. (IEEE link.)
^{ (Image from Stefan Huber.) }