Is drawing the Voronoi diagram NP-hard? Suppose we have  a set of points in the plane. Is computational complexity defined to draw the Voronoi diagrams of these points?
Since the plan is continuous I don't see how complexity can be defined. Please explain.
On the other hand if we discretize the space into small cells and attempt to associate each cell with the closest point to approximate the Voronoi diagram, is it NP-hard? Because this looks like minimum distance decoding, which I think is NP-hard. 

To address your first question, the ordinary discrete notion of NP-hard indeed does not apply to continuous problems such as this one. On the other hand, there is a theory of computational complexity for problems with continuous data: look up Blum-Shub-Smale machines. 
