DISTANCE_TO_POSITION_SPHERE
Estimate city positions from distances on a sphere.

DISTANCE_TO_POSITION_SPHERE is a MATLAB program which estimates the positions of cities given a city-to-city distance table. The cities are presumed to lie on a sphere, and to be sufficiently separated that the curvature of the sphere must be accounted for.

The problem is singular. In particular, the position of one city is completely arbitrary, and one component of a second city is completely arbitrary (and a third city's position can be "flipped" about the line connecting cities one and two). To remove some of this singularity, the program assigns city #1 to have latitude and longitude 0, and city #2 is given a longitude of 0.

Once the nonlinear least squares problem is set up, MATLAB's LSQNONLIN function is called to seek a solution.

Note that if the cities are all in a relatively small area, it may be reasonable to treat the problem as though it were posed on a plane.

If your data is on the earth, note that the average radius of the earth is 3,959 miles or 6,371 kilometers.

Acknowledgement:

The selection of MATLAB's LSQNONLIN function for use as the solver, the construction of the appropriate anonymous function, and the setting of the options for LSQNONLIN were devised by Gene Cliff, to whom grateful acknowledgement is made.

Usage:

distance_to_position_sphere ( 'distance.txt', radius )

• 'distance.txt' contains the distance table
• 'radius' is the radius of the sphere

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

CITIES, a dataset directory which contains sets of information about cities and the distances between them;

CITIES, a FORTRAN90 library which handles various problems associated with a set of "cities" on a map.

DISTANCE_TO_POSITION, a MATLAB program which estimates the positions of a number of cities based on a table of city-to-city distances, assuming Euclidean geometry.

LAU_NP, a FORTRAN90 library which implements heuristic algorithms for various NP-hard combinatorial problems.

NMS, a FORTRAN90 library which includes a wide variety of numerical software.

PARTIAL_DIGEST, a FORTRAN90 library which solves the partial digest problem.

Reference:

1. John Hartigan,
   Clustering Algorithms,
   Wiley, 1975,
   LC: QA278.H36,
   ISBN: 0-471-35645-X.

Source Code:

• distance_to_position_sphere.m, the source code.

Examples and Tests:

HA30 is a dataset of spherical distances for 30 cities, as selected by Hartigan from the World Almanac, 1966.

• ha30_name.txt, the names of the cities.
• ha30_dist.txt, the distance table for the cities. Distances are measured in hundreds of miles.
• ha30_output.txt, printed output in response to the command

  distance_to_position_sphere ( 'ha30_dist.txt', 39.59 )

• ha30_dist.latlon.txt, the latitudes and longitudes (in degrees) that best fit the distance table.
• ha30_dist.xyz.txt, the XYZ coordinates corresponding to the latitudes and longitudes.
• ha30_dist.dist2.txt, the distance table, as recomputed from the latitudes and longitudes.

You can go up one level to the MATLAB source codes.