Voronoi Tesselation on a Mesh

So I did a little googling and it seems that there are two ways most people create a voronoi tesselation on a surface (NURB). The first being a UV mapping method in which points are seeded on the surface and mapped to the XY plane where a voronoi diagram is generated and then these curves are then mapped back onto the original surface. The second being an intersection between 3D Voronoi cells generated by points on the surface and the surface itself.

Unfortunately for me, I have a mesh and not a surface (a complex mathematical surface which I exported out of another program, I do not understand the math behind it). I tried to emulate the second method. I deconstructed the mesh and at random chose vertices on the mesh and used those vertices to create 3D Voronoi cells. I then deconstructed the cells to obtain the curves and intersected these curves with the mesh. Unfortunately this yields a list of list of points (for each curve). Each list of points inside the list of list of points has at most 2 intersections (most have 1). Creating a curve from 3 points is out of the question and even if I wanted flat voronoi cells, it would still be out of the question considering some curve intersections only have 1 point.

So my question are: Am I doing something obviously wrong? Is it possible to UV map curves on to a mesh (to emulate the first method)? Should I convert the mesh to a polysurface (I'd rather not, the mesh has many faces) and then go about using the methods described above and are there complications if it is a polysurface? Are there some amazing plugins that I haven't found that will help me?