0

I have a set of points (4 or more points per set) placed in a 3D euclidian space. The points are all on the surface of a unit sphere and relaxed to place them as far away from each other as possible, if that makes a difference. I want to construct a graph of the points, where each point is connected to all of its natural neighbors. How can I test if any two points are a natural neighbor?

Since the number of points is relatively few and this calculation needs to be performed only once per set I figured I would just iterate through all possible connections (pairs of points) and determine if that connection was acceptable. This has proven tricky due to my limited mathematical understanding. I would really appreciate it even if you just mentioned the search terms I am looking for.

Sum-Won
  • 1
  • 1
  • 1
    What are 'natural neighbors'? – kcsquared Feb 13 '22 at 13:43
  • Isn't every point a neighbor of every point on a sphere? – Good Night Nerd Pride Feb 13 '22 at 13:45
  • Upon searching the term, I've learned this likely refers to [natural neighbor interpolation](https://en.wikipedia.org/wiki/Natural_neighbor_interpolation), where two points in Euclidean space are 'Natural neighbors' if they share an edge in the Delaunay triangulation. Still, it seems like a specialized enough term that including a definition and example here would be helpful, especially if you're using a different metric than the standard Euclidean one. – kcsquared Feb 13 '22 at 13:59
  • 1
    @kcsquared It seems your reference is only valid with euclidian space 2D or 3D, BUT NOT a sphere which is topologically different. I found this beauty, "by the way": https://stackoverflow.com/questions/9600801/evenly-distributing-n-points-on-a-sphere – Fredy Feb 13 '22 at 15:00
  • The metric is still euclidian. The points just happen to be positioned on the surface of a sphere. The connections between them would not follow the surface of the sphere, but would cut below it. As long as the number of points is large enough it would let me approximate a sphere well enough for my needs. – Sum-Won Feb 13 '22 at 18:14
  • I think I figured it out. What I want is to determine if the Voronoi cells of any two points share a surface. I am of course way too dumb to produce a 3D Voronoi graph, but I don't have to. I can place a point half-way between the two candidate neighbors and then determine if any other point is closer to the point than the candidate points are. If such a point exists, then the half-way point can not be at a surface of a Voronoi cell, meaning the two points are not neighbors. – Sum-Won Feb 13 '22 at 19:00

0 Answers0