@complexring!
Sorry for a long time answer.

My message: it's may be bad idea to calculate distance between points on embedded surface as Euclidean metric. For example, take a look for sphere (Earth): Euclidean distance between north pole and south pole equal to 2R, but you can't penetrate through the Earth! You must keeping aboard surface, and, in this case, the real distance between point is equal to \pi * R.

Close point, obviously, should have similar properties, so you need to use a local metric.But of course it is necessary to take a closer look into the details of the task.e details of the task.