"Enhanced" random-color generator?

May 4, 2013 at 4:26 AM
The following obit in the Los Angeles Times reminded me of a suggestion I made for enhancing 4.8's random-color generator.

In 4.8, the generator can inadvertently give the same color to adjacent shapes, making it hard to distinguish them.

I suggested that this could easily be averted, since as few as four colors would suffice to color a map in such a way that no two adjacent shapes had the same color.

A discussion of the proof of this theorem is included in the obit, below.

This enhancement would be an excellent addition to 4.9, if not already included.


Roy Lipscomb

(The following obit starts about half way down the webpage.)

Kenneth Appel

Proved a major math theorem

Kenneth Appel, 80, a mathematician who paired with another scientist to become the first to use a computer to prove a major mathematical theorem, died April 19 in Dover, N.H., according to the Tasker Funeral Home. He had esophageal cancer.

Appel was a longtime educator who chaired the University of New Hampshire mathematics department, retiring in 2003. Before that, he was a faculty member at the University of Illinois at Urbana. In 1976, he and Wolfgang Haken used 1,200 hours of calculations from an IBM computer to prove that a flat map can be colored with only four colors, so that contiguous countries have different colors.

Proving the 100-year-old "Four-Color Conjecture" was considered a major achievement at the time, though highly unpopular with some mathematicians who did not trust the performance of computers, and voiced their concerns for years afterward.

As a 1982 Times story put it, "In the absence of checkability, is the proof valid? How can we be sure the computer did what we thought it did? How can we be sure that it didn't make a mistake? What does it mean to have proofs that people cannot examine?"

Appel and Haken received the American Mathematical Society and the Mathematical Programming Society's Delbert Ray Fulkerson prize in 1979.

Since retirement, Appel counseled students at Dover High School, helping to set up an Internet-based homework system, and served on the Dover Board of Education.

Born Oct. 8, 1932, in Brooklyn, N.Y., Appel grew up in Queens and graduated from Queens College in 1953 with a bachelor's degree in mathematics. He worked as an actuary before serving two years in the Army. After his discharge he earned a doctorate in mathematics from the University of Michigan, then did research in cryptography at the Institute for Defense Analyses before moving on to the University of Illinois.

Los Angeles Times staff and wire reports

news.obits@latimes.com Copyright © 2013, Los Angeles Times
May 6, 2013 at 7:01 AM
Edited May 6, 2013 at 7:13 AM
Hi Roy,

This sounds great.
Do you have C++ skills? If so you could provide a patch that will replace our current random colour routine with yours.

Here's some more background information:

Perhaps using 4 colors isn't needed for MapWindow but the idea of no two adjacent shapes get the same color is interesting.


May 16, 2013 at 9:26 PM

Sorry, my programming skills are outdated. I never even learned C. But I'm guessing the algorithm for the above shouldn't be too hard to code:
  1. Pick a random color for this shape, other than a color already tried for this shape.
  2. If an adjacent shape is using that color, go to step 1.
My reference to four colors being the maximum needed was intended only to point out that MapWindow, with its much broader color palette, will find the above algorithm a breeze.



P. S. Sorry this is so late. I didn't get your response by email, and only today did I think of checking the website.
May 17, 2013 at 6:22 AM
Hi Roy,

We will take it along when we'll work on v4.9