More concretely, I think the algorithm referenced above, that involves solving a system of linear equations, will work just as well for the $N < M+1$ case, though the matrix is no longer square. Assuming the system has a solution, then the point $p$ obtained is the center of the (translated) sphere, and hence the equidistant point you seek.

If three distinct points lie on a line, then no point is equidistant to them. If they don't lie on a line, then a unique circle passes through them; its center is the unique equidistant point. The same is true in general. We need to check that the $N$ points are in "general position", i.e., that they don't lie on a hyperplane of dimension lower than $N-1$. Three points shouldn't lie on a line, four points shouldn't lie in a plane etc. If the $N$ points are in general position, then a unique hypersphere passes through them; its center is the equidistant point.

Your answer makes clear that every connected graph is $n$-almost Hamiltonian for all even $n$. Is there a chance that some graphs, such as all cubic graphs, are $n$-almost Hamiltonian for some odd $n$?

I notice that of the 11 unfoldings of the cube, 2 have mirror symmetries and the other 9 do not. If we count the "chiral" pairs separately, then we have a total of 20 unfoldings. From the beautiful figures in two of the answers, it is difficult for me to tell how many of the 261 unfoldings of the 4D hypercube have mirror symmetries. Does someone know?

There is a short non-paper called "The geometry of circles: Voronoi diagrams, Möbius transformations, Convex Hulls, Fortune's algorithm, the cut locus and parametrization of shapes" (maybe it was part of a grant proposal?) in which David Dobkin and Bill Thurston discuss Voronoi diagrams and several related topics. In it they point out that the combinatorics of the Voronoi diagram are, to large degree, invariant under any Mobius transformation, though such a transformation will change its geometry.

There are certainly (somewhat generic) cases in which non-uniform scaling transforms a point set and its VD in a consistent manner. For example, Z^n and its VD can be scaled non-uniformly in orthogonal directions and remain consistent. Another interesting question (though probably not @Oskar's question) might consider which transformations preserve the VD's combinatorial structure. This does not seem obvious to me, even for the simple case of a lattice. If answers to these questions are already known, perhaps the question can be considered merely asking for a reference.

This question does not appear off-topic. Perhaps the preamble "I'm a programmer..." led some to this conclusion. The question can be understood in one of two senses. (a) Under what transformations of a set of points and their Voronoi diagram does the transformed VD remain the VD for the transformed set of points? (b) Under what transformations does a VD remain a VD for some, possibly different, set of points. It's not obvious to me that the answers to these question must be the same.