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. 
 A: It's true that the plane is continuous, but the Voronoi diagram consists of finitely many polygons. Moreover, the vertices of those polygons have coordinates that are rational functions of the original set of points. So the computational complexity of Voronoi-diagram computation is well-defined; you just have to be in a computational setting where you can do arithmetic on your original coordinates. In particular, the Voronoi diagram of a set of points with rational coordinates itself has rational coordinates, so you can do everything with integer arithmetic and the standard notion of NP-hardness does apply.
In fact, computing a Voronoi diagram on $n$ points in $\Bbb{R}^d$ can be done in time $O(n \log n + n^{\lceil d/2 \rceil})$ (see page 30 of this paper). So the problem of computing planar Voronoi diagrams can't possibly be NP-hard; on the other hand, the problem of computing Voronoi diagrams in arbitrary dimensions may very well be...
A: 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. 
