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?
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
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.)