"kosma@ALAN.LAAC-AI.Dialnet.Symbolics.COM"@alan.kahuna.decnet.lockheed.com (07/08/89)
Received: from GEORG.LAAC-AI.Dialnet.Symbolics.COM by ALAN.LAAC-AI.Dialnet.Symbolics.COM via CHAOS with CHAOS-MAIL id 28908; Fri 7-Jul-89 14:32:47 PDT Date: Fri, 7 Jul 89 14:32 PDT From: Montgomery Kosma <kosma@ALAN.LAAC-AI.Dialnet.Symbolics.COM> Subject: The four color problem (was Re: Re: Clicking on Irregular Shapes (and the four color problem)) To: "eagle::amiga-relay%udel.edu"@KAHUNA.LAAC-AI.Dialnet.Symbolics.COM In-Reply-To: Your message of 7 Jul 89 14:12 PDT Message-ID: <19890707213242.8.KOSMA@GEORG.LAAC-AI.Dialnet.Symbolics.COM> In article <54160@tut.cis.ohio-state.edu> Jeff Martens <martens@ketch.cis.ohio-state.edu> writes : Probably not good maps then -- the US is not 4-colorable. Consider West Virginia, Ohio, and Wyoming, for example. They each have more than 4 neighbors. A map's "goodness" may be a rather subjective measure but if what you refer to is the ability to color a map without having neighboring states/areas using the same color, it seems that you missed something. A state having more than four neighbors does NOT mean that it requires MORE than four colors to prevent neighboring states from having the same color. For example, imaging the following state FOO which has several neighbors as sketched below: BAR --- XYZZY --- PLUGH | \ | / | | FOO | | / | \ | FROOP ----------- SCUMDOGGIE clearly (well, somewhat clearly) FOO has 5 neighbors. Now, imagine colors indexed from 0 to 3...this arrangement can be colored as follows: 0 1 2 3 1 0 It's rather easy to see that with a simple case like this only four colors are needed. Now I'm not positive of all the aspects of it, but the four color theorem says basically that four colors are enough for maps which do not have such features as non-contiguous regions (and the example usually given is of a region which has two parts, one of which is enclosed by another region--like when you want to color the space around a doughnut and the space in the hole of the doughnut the same color). I don't know if this causes a problem when coloring the US--I suspect that if you allow one further color for bodies of water, then four colors for all of the states will suffice. Montgomery N. Kosma disclaimer: this has nothing to do with Lockheed--I'm just hanging around saving a world on one of my lispms.
doug@xdos.UUCP (Doug Merritt) (07/09/89)
In article <19250@louie.udel.EDU> "kosma@ALAN.LAAC-AI.Dialnet.Symbolics.COM"@alan.kahuna.decnet.lockheed.com writes: >are needed. Now I'm not positive of all the aspects of it, but >the four color theorem says basically that four colors are enough for maps >which do not have such features as non-contiguous regions (and the example >usually given is of a region which has two parts, one of which is enclosed >by another region--like when you want to color the space around a doughnut >and the space in the hole of the doughnut the same color). I don't know if >this causes a problem when coloring the US--I suspect that if you allow one >further color for bodies of water, then four colors for all of the states >will suffice. Good point. I screwed up in my previous posting on the subject, because I was thinking about Alaska and Hawaii as the "noncontiguous" portions, and they do *not* cause problems. You can still 4-color such a map, even including using one of the four colors for the ocean. What can cause a problem is the example in another posting of a state split by a great lake (Michigan)...both halves of the state must be the same color, and this additional constraint could make the map non-4-colorable, depending on surrounding configurations. Looking at a map of the US, it's difficult to see whether Michigan is in fact a problematic configuration, but it may be. Doug -- Doug Merritt {pyramid,apple}!xdos!doug Member, Crusaders for a Better Tomorrow Professional Wildeyed Visionary
cosell@bbn.com (Bernie Cosell) (07/09/89)
In article <427@xdos.UUCP> doug@xdos.UUCP (Doug Merritt) writes: }In article <19250@louie.udel.EDU> "kosma@ALAN.LAAC-AI.Dialnet.Symbolics.COM"@alan.kahuna.decnet.lockheed.com writes: }>are needed. Now I'm not positive of all the aspects of it, but }>the four color theorem says basically that four colors are enough for maps }>which do not have such features as non-contiguous regions ... } }What can cause a problem is the example in another posting of a state }split by a great lake (Michigan)...both halves of the state must be the same }color, and this additional constraint could make the map non-4-colorable, }depending on surrounding configurations. } }Looking at a map of the US, it's difficult to see whether Michigan }is in fact a problematic configuration, but it may be. No problem. Since there is no *other* state separating the two parts of michigan, you can make a modified US map with the Michigan and UP connected by an infintessimal thread. this thread will not cut any other state and so you now have a normal, four-colorable map, and so you four color it. the thread will make the two parts of michigan act as a single connected region and so be colored with a single hue, and then just use THAT coloring for the original map. Bodies of water are more complicated because unlike governmental boundaries, they don't really start and end, but really just interconnect to form huge serpentine regions that cut the land-regions into assorted discontiguous shapes. The entire Mississippi/Missouri complex wouldhave to be a single color, and Louisiana, for example, would be divided into a zillion not-connected pieces. I suspect, though, that even with considering connected bodies of water as regions (even though that gives you disconnected land regions), you can still four-color the whole mess. I'm *sure* that if you consider ALL bodies of water as a *single* (of necessity disconnected) region, then you're sunk. /Bernie\