Conference rusure::math

994.0. "how well can zipcodes be assigned to reflect relative distance" by LEVEL::OSMAN (type hannah::hogan$:[osman]eric.vt240) Wed Dec 14 1988 15:38

The following problem may be related to my previous puzzle about
circles expanding into polygons.

Consider a map of a country divided into towns.

It is your job to assign zip codes to these towns in an optimal way
such that, as much as possible, the numerical difference between the
zip codes of any two towns reflects the number of intervening towns including
one of the endpoints.

No gaps are allowed.  So, assuming there are n towns and you start
numbering from 1, the highest zip code will be n.

How well can you do ?

Obviously, the answer will depend on the geography.  For example, if
the towns are strung along in one dimension, like this:

	1 2 3 4 5

then we can assign zipcodes 1,2,3,4,5 respectively, and we get a perfect
score.

How about towns in a square country like this:

	1 2
	3 4

In this country, if we assign zipcodes as illustrated, 1-2 is good,
1-3 not so good (it also wants to be 1-2).  3-4 is good, 2-4 not as good.
We must establish agreement about diagonals.  Are there no intervening
towns between 1 and 4, or do we say one is forced to travel through either
2 or 3 to get to 4.

If we are forced to travel through 2 or 3, then there's one intervening
town between 1 and 4, which makes the 1-4 zipcode assignment a little
better than if we treat towns 1 and 4 as adjacent.

How well can larger square arrangements be assigned?

How well can more random arrangements be assigned (such as the towns
generated by the expanding circles in my previous posting) ?

Thanks.

/Eric

    This may be related to the problem the telephone company faces
    in computing tariffs for calls routed through the network.

    They base their solution on minimum spanning trees; these are
    not optimal, but the optimal form, the Steiner tree, is NP-hard
    to compute.

    By the way, the dual of the Voronoi diagram, (variously known as
    the Delaunay or Thiessen triangulation), is probably a better way
    to represent the adjacency of the towns.

    See Preperata and Shamos, "Introduction to Computationa Geometry"
    for relavent material.

    - Jim

    Re .1:
    
>    This may be related to the problem the telephone company faces
>    in computing tariffs for calls routed through the network.
>
>    They base their solution on minimum spanning trees; these are

    Do you mean how they compute their own cost?  When I worked in
    Telephony about 3+ years ago long-distance tariffs in the US and
    Canada were based solely on distance.

    --  Barry

    Is this a theoretical problem that wants some estimate of how 'bad'
    an assignment may be?  If so, then you might want to use R^2 distances,
    and the triangle inequality.

    Maybe this is a good job for simulated annealing...

    - Jim