The principal data set used by the programs in this section of Nemo Librray API examples consists of close to two million points, distributed over the planetary surface with local density matching the system activity level of a typical computer application that deals with the "where of things" related the human population.
The data set is distributed by the Department of Combinatorics and Optimization at the University of Waterloo as a text file of 1904711 point φ, λ coordinates, in angular degrees to four decimal fraction digits: Thus the ground resolution of coordinates is approximately 10 meters along the meridian. The text file is approximately 45 MB in size, compressed down to 11.5 MB for distribution.
Programs in this section use the same set of points, in a "flat" array of binary (64-bit unsigned integer per point) UniSpherical coordinates. This representation yields isometric ground resolution of between 5 and 15 millimeters, in a file of about 15.2 megabytes. (w1904711.p8b [Downoad]). The array is ordered on the numeric point coordinate. An animated planetography depiction of the data set can be seen [here].
Included C language program (csvToP8b.c - [source], [Linux executable] reads a .csv distribution file and creates the binary UniSpherical coordinate file. (For usage and functionality of every program presented on this page, see the commentary in the program source).
Next in the series is a short program (listP8b.c - [source], [Linux executable] that traverses the binary array and prints coordinates on the console. The two programs together demonstrate the reading and writing both text and binary form of UniSpherical coordinates in external files (or network streams).
As mentioned in the introduction, the data set described and depicted above has been published in the context of solving the well‑known combinatorial geometry proposition: the Travelling Salesman Problem. As the Wikipedia article suggests, "...The nearest neighbour algorithm was one of the first algorithms used to solve the travelling salesman problem approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. The algorithm quickly yields a short tour, but usually not the optimal one".
The included program nearNextP8bBruteForce.c - [source], [Linux executable] creates the "nearest next" itinerary by "brute force" in situ sort: at any city the salesman finds himself along in the itinerary, he evaluates the distance to all cities not visited so far, and selects the nearest to be the next in his itinerary. The sort algorithm is extremely simple, as it does not assume any location-specific order of input coordinate array. (As above, the commentary provides the details).
Although the UniSpherical coordinates ensure that the distance calculation between the two planetary locations is extremely fast, the program takes a long time - close to 32 000 seconds (almost 9 hours) - seconds to create the itinerary for 1.9 million locations ("cities").
In the search for an approximate "nearest neighbor" itinerary, it is possible to take advantage of UniSpherical coordinate natural "location clustering". Instead of searching for the next city among all the remaining un‑visited cities, we can restrict the search to block (a "window") of cities that occur in the array ordered by UniSpherical coordinate number. That strategy might (or might not, depending on the spatial distribution of the input data) increase the total itinerary length but accelerate the search. Size of the search window will shift the balance between the speed and the the quality of the solution. This approach, which takes advantage of the numerical structure of UniSpherical coordinates, in implemented in nearNextP8bWindow.c - [source], [Linux executable].
As is obvious from the inspection of the source code, the implementation is more complicated than the previous example. However, the increase in the execution speed is dramatic: the construction of itinerary connecting 1.9 million points is reduced from 9 hours down to slightly over 42 seconds. (Doubling the search window (approximately) doubles the execution time, with only a few percentage points reduction in the itinerary length - this further demonstrates the benefits of spatial clustering of UniSpherical coordinate numbers).
In the texts on Travelling Salesman Problem, the "nearest‑neighbor‑next" if often described as the algorithm taken by a "naive traveller". We can speculate about an extremely naive traveller that does not even know how to calculate "as‑the‑crow‑flies" distance between two cities; he might simply sort the list of the cities to visit by their UniSpherical coordinates and start from the top. To his surprise, the itinerary length would be better than spending 9 hours doing the brute force nearest neighbor search!