# Delaunay triangulation and relative-neighborhood graph on the sphere

## Notes

1

Create n nodes in random positions on the unit sphere.

Input

Count of nodes

2

Create the Delaunay triangles that are formed by the nodes created in step 1.

Computation time scales with the fourth power of the count of nodes: the circumcircle of every trio of nodes (1, 2, 3) must be checked against every node that could be inside that circumcircle (4), in order to determine whether the circumcircle forms a valid triangle. According to Wikipedia, this could be reduced to n2 or even nlog(n), but I don't care enough to figure out flipping algorithms on the sphere at this time. (Note: Creating the SVG map seems to scale slower than linearly as well.)

3

Create the edges that compose the Delaunay triangles created in step 2.

4

From among the edges created in step 3, find those that are part of the relative-neighborhood graph.

5

Not implemented at this time

From among the edges found in step 4, find those that are part of the minimum spanning tree.

6

Project all the nodes and edges onto a two-unit cube with the gnomonic projection, unfold the cube so that all faces are coplanar, and display the result as an SVG file.

Output

List of nodes

List of triangles

List of edges

The trio of coordinates given for a triangle indicates the circumcenter of that triangle—i. e., the location of the Voronoi node that corresponds to that Delaunay triangle.

All longitudes and latitudes are given, not in degrees, but in radians.

In maps that contain only a few nodes, every edge that crosses more than one face boundary will be drawn either incorrectly (the short arc rather than the long arc) or not at all. To fix this problem, increase the node count.

## Output

Estimated time to finish stage: 0 seconds

Map

Off-map color:
Grid color:
Delaunay nodes color:
Delaunay edges color:
Delaunay edges subset:
Voronoi nodes color:
Voronoi edges color:
Voronoi edges subset:

List of nodes

List of triangles

List of edges