Estimate city positions from distance tables.

**DISTANCE_TO_POSITION**
is a MATLAB program which
estimates the positions of cities given a city-to-city distance table.

In 2D, 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 the position (0,0) and city #2 is given a zero Y coordinate.

In N-dimensional space, a similar set of constraints must be placed on the first N cities, or the least squares solver is likely to fail. (That is, we specify all N components of the first city to be 0, N-1 components of the second one, and so on, up to the N-th city which has a single zero component).

The computations carried out by this program assume that the cities lie on a plane. If the distance data is for international cities, the effect of spherical geometry may make the planar approximation very bad.

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

reads the distance information indistance_to_position('distance.txt')

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

**DISTANCE_TO_POSITION** is available in
a FORTRAN90 version and
a MATLAB version.

CHAIN_LETTER_TREE, a MATLAB program which analyzes a similarity matrix for 11 versions of a single chain letter and produces a dendrogram or tree diagram that suggests the degrees of relatedness and the evolutionary history of the letters.

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

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

DISTANCE_TO_POSITION_SPHERE, a MATLAB program which estimates the positions of cities on a sphere (such as the earth) based on a city-to-city distance table.

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.

- distance_to_position.m, the source code.

**CHAIN_LETTER** is a problem involving perceived distances between
pairs of 11 chain letters.

- chain_letter_distance.txt, the distance table for the chain letters.
- chain_letter_distance.png, a plot of the estimated positions of the chain letters.
- chain_letter_distance.coord.txt, the estimated positions of the chain letters, based on the distance table.

**GRID04** is a problem involving distances between pairs of 4 points.

- grid04_xy.txt, positions of 4 points on a grid.
- grid04_xy.png, an image of the 4 points on a grid.
- grid04_dist.txt, the distance table for the points.
- grid04_dist.coord.txt, the estimated positions of the points, based on the distance table.

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