Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!apple!agate!eris.berkeley.edu!mwm
From: mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer)
Newsgroups: comp.sys.amiga.tech
Subject: Maps & mathematics (Was: Re: Clicking on Irregular Shape)
Message-ID: <26691@agate.BERKELEY.EDU>
Date: 27 Jul 89 14:47:17 GMT
References: <635967196@hpindwa.HP.COM> <387100007@S41.Prime.COM>
Sender: usenet@agate.BERKELEY.EDU
Reply-To: mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer)
Organization: Missionaria Phonibalonica
Lines: 73

In article <387100007@S41.Prime.COM> CIS@S41.Prime.COM writes:
<Indeed.  What makes the geo map of the US not a mathematical map?

Hmm. A map in mathematics is a function that takes elements from one
set to a second set. Somehow, I don't see how any geographical map can
do that.

<There is
<an isomorphism between any geo map and a mathematical graph:
<
<states -> nodes
<borders -> arcs (or edges, depending on which textbook you read)

First, a "mathematical graph" isn't a "mathematical map".

Second, that doesn't work. You've only dealt with borders that touch
exactly two states. The US has state borders that touch as few as one
and as many as four states. You also have to decide what to do about
Michigan, which has two disconnected regions.

Every planar map can be described by a graph. But see the assumptions
below about what a "planar map" is. If you replace the word "states"
with "regions", and include everything not in the map as one region,
then you've described how to find the graph for which this is the
geometric dual (mathematical maps can be isomorphic; the map from
planar maps to graphs isn't isomorphic unless you include multigraphs.
In any case, the sets being mapped are isomorphic, not the elements of
those sets).


Of course, if by "mathematical map" you mean "map in the sense of the
four color map theorem" (considering the old topic, this is likely) or
"planar map" then the US is not such a map. There are at least two
constraints violated by a map of the contiguous 48 states.  1) every
region must be contiguous (Michigan isn't), and 2) regions meet only
at edges, not at corners (the four corners isn't an edge) (*).

Of course, that doesn't mean you can't color a map of the US with four
colors. Only that theorems about map-coloring don't tell you whether
or not you can do so.

<It is not a complete graph, though, because no arc exists connecting Hawaii to
<the lower 48  or Alaska to the lower 48.  No assumption is made about the
<shape of the units to be colored in a mathematical map, so there goes a
<particular argument there (against the US map being a mathematical map).

You should get your terminology straight. A "complete" graph is one
where every vertex (or node, if you used a different textbook) is
connected to every other vertex, and usually denoted by K subscript n,
for the complete graph on n points. The graph you're trying to
describe obviously isn't complete. Nor is it "connected", meaning that
there's a path from every node to every other node.

<Try it some time.  I think that you'll find that the US map is a
<mathematical map.

No way. No how.

However, the US map can be colored in four colors. Cartographers do it
all the time.

	<mike

(*) an alternative statement of the 4color map theorem allows regions
to meet at points, but doesn't consider them adjacent in that case.
This is clearly unacceptable for doing hit detection on irregular
shapes, so I didn't use it.

--
The weather is here, I wish you were beautiful.		Mike Meyer
My thoughts aren't too clear, but don't run away.	mwm@berkeley.edu
My girlfriend's a bore, my job is too dutiful.		ucbvax!mwm
Hell nobody's perfect, would you like to play?		mwm@ucbjade.BITNET