Compartilhar via

Whidbey Island And Bagel Mathematics

  • Artigo

I was highly amused to read on Raymond Chen's blog the other day that mathematicians are hard at work solving the problem of how to most evenly distribute poppyseeds over a bagel. The reason I was highly amused was not just the whimsical description of what is actually a quite practical and difficult problem.

And yes, believe it or not, it is a practical problem; if you can figure out how to distribute points evenly around an arbitrary shape then you can use that information to develop more efficient computer algorithms to solve complex calculus problems that come up in physics all the time. There are also applications in computer graphics, I'd imagine; 3-D modeling frequently requires generating well-behaved finite approximations of a surface.

But I digress. The other reason I was highly amused is that Whidbey Island is the longest island in the United States.

OK, obviously I should explain that one, as the connection between mathematicians, bagels and Whidbey Island may not be immediately apparent.  But first, yes, I know that Whidbey Island is NOT the longest island in the United States -- not that anyone here in Washington State will admit to it.  As this page points out, by any reasonable measurement Whidbey Island is shorter than Long Island, Hawaii and almost two dozen islands off the coast of Alaska.  Whidbey Island's real claim to fame is that it is the longest island in the United States that is also in the Pacific Ocean but not part of Alaska or Hawaii -- big whoop.

Anyway, when I first moved here I did a bicycle trip around the southern lobe of Whidbey Island, and plenty of people told me lies about Whidbey Island being the longest island in the United States.  Which got me wondering how exactly that would be measured.

This led to a spirited email debate amongst my various math geek friends. The page I referenced above gives three definitions for island length, all vague and imprecise:

  • if the island is "narrow and straight" then "it's easy" to determine what the length is.
  • if the island is "rounded" then the longest distance to "opposite shores" is the length.
  • if the island is "bent", like Whidbey, then draw a bent line "down the middle" and measure that.

I didn't like any of these then, and I don't like them now.  There should be one unambiguous standard for length that doesn't rely upon vague and imprecise notions like "opposite shores", or "down the middle".

The standard should also work for really weird-shaped islands.  Consider for example an island which is a narrow ring.  Say, a circle with a circular lake in the middle.  None of the algorithms above are satisfactory. That island should be longer than an island with the same size and shape but no lake in the middle. In the island with the lake in the middle you can't walk in a straight line from one side to the other, so the island should be longer. Similarly, islands like Whidbey that are bent should be longer than straight islands.  Or, put another way, taking a long, straight island and bending it into a spiral should not change its length drastically.

Here's how I define the length of an island:  consider every pair of points on the perimeter of the island.  Clearly there are an infinite number of pairs of points, but we won't let that deter us.  Pick a pair.  Now consider every possible path, no matter how twisty-turny, that connects those two points, with the restriction that the path must be entirely on the island at all times.  Clearly, there's an infinite number of those too.

But of that infinite number of paths between the two points, at least one of them has to be the shortest.  (There could be two or more equal shortest paths, if, say, you could go both ways around an internal lake to get from point A to B, but whatever, pick one of them.)  Of course, for most of them it will be a straight line, but on weird shaped islands, it might have to bend here and there.

Now, find the pair of points where the shortest distance between them is as long as possible.  That is, find the two points on the shore where, even if you took the shortest path between those points, you'd still have to walk farther than if you took the shortest path between any other pair of points.

That distance, the length of the longest shortest path, is the length of the island. 

Of course, finding those points and the shortest path between them might be a difficult problem if the island is a really strange shape.  But that's just a technical detail that we can wave away; we have an impractical but formal definition, and that's what matters to me when I'm wearing my mathematician hat.

What does this have to do with the bagel algorithm?

Imagine all the possible distributions of, say, a thousand points around a "manifold".  (Which is just a fancy way of saying "shape" for our purposes; a more technical definition would take too long.)  Suppose the manifold is the surface of the earth.  Obviously there are an infinite number of such distributions, and an infinite number of them are going to be really, really sucky from the perspective of spreading them around evenly. 

Like, any configurations in which all of the points are on Whidbey Island, for example. 

For each of those distributions of a thousand points, pick every pair, and again, consider every path between each pair, where the path stays on the manifold. For every pair, find the shortest path, and then find the pair that has the shortest shortest path. 

If all the points in a given configuration are in Whidbey Island, maybe the shortest shortest path is one centimeter, maybe it's one meter, but you are guaranteed that the shortest shortest path is quite a bit smaller than the length of the island!

Now work out the shortest shortest path for every possible configuration of points.  At least one of those configurations has got to have the longest shortest shortest path, and that configuration is the desired configuration.  It's the configuration of points where the smallest possible distance between the two points that are closest together cannot be made larger without making some other pair of points become even closer together than the original pair.  You simply can't get any better than the configuration with the longest shortest shortest path. 

Of course, finding that configuration out of the infinite number of possibilities is a non-trivial problem. But clearly the "find the length of the island" problem is just a very simple version of the bagel problem.  It's got only two points and a Whidbey-Island shaped manifold, rather than a thousand points and a bagel-shaped manifold. If you can solve one, you can solve the other!

And while we're on the subject of island superlatives and ridiculous phrases like "the longest shortest shortest path", I should point out that Canada is home to not only the largest island in a freshwater lake in the world, but also home to the largest island in a lake that is on an island in a lake! Anyone care to hazard a guess at what they are?

Comments

  • Anonymous
    December 14, 2004
    Google is your best friend.

    1. [http://www.kayakplace.com/places/plnchnl.htm] Manitoulin is the largest island in the Great Lakes, and, for that matter, the largest island in a freshwater lake anywhere.

    2. [http://www.geocities.com/statesaz2/Michigan.html] Ryan Island in Siskiwit Lake on Isle Royale in Lake Superior is the largest island in a lake on an island in a lake (bet you have to reread that!).

  • Anonymous
    December 14, 2004
    Being from Ontario, this is an easy one.

    The largest freshwater island is Manitoulin Island in Lake Huron.

    The largest island in a lake on an island in a lake is Treasure Island in Mindemoya Lake, also on Manitoulin Island.

  • Anonymous
    December 14, 2004
    Actually, according to http://users.erols.com/jcalder/SUPERLATIVESV2.html the largest island on an island is in Indonesia:

    "Island on an island

    The largest island on another island is Pulau Samosir, in Lake Toba on Sumatra, Indonesia. Samosir is 245 sq mi / 630 sq km, and is inhabited.

    There are several places where islands on islands in turn have lakes with islands - triple islands."

  • Anonymous
    December 15, 2004
    Indonesia isn't on a lake.

  • Anonymous
    December 15, 2004
    "Ryan Island in Siskiwit Lake on Isle Royale in Lake Superior is the largest island in a lake on an island in a lake..."

    But is it the longest island in a lake on an island in a lake, or even the largest island in a lake on the longest island in a lake?

    Could it be the largest island in a lake on an island in the longest lake?

  • Anonymous
    December 15, 2004
    Now my brain hurts.

    I had always heard that Treasure Island was the largest island-in-a-lake-in-an-island-in-a-lake. How big is it compared to Ryan Island, anyone know?

  • Anonymous
    December 15, 2004
    Thanks for a great article, Eric.

    Ometepe (in Lake Nicaragua) is supposed to be the world's largest island in a freshwater lake. It gets additional cool points for having two volcanos; one is still active .. the other has a lagoon inside it :)

  • Anonymous
    December 15, 2004
    The comment has been removed

  • Anonymous
    December 16, 2004
    Just as a terminology note, when you talk about the longest shortest path you're talking about what graph theorists call <i>diameter</i>. The usual construction goes something like:

    * Define the distance between any two points (which you're doing using lengths of paths)
    * Define the <i>eccentricity</i> of a point as the maximum of all distances between that point and other points in the graph.
    * The diameter is then the maximum eccentricity. There's a related concept -- the radius -- which is the minimum eccentricity: the shortest longest shortest path, in a sense.

  • Anonymous
    December 16, 2004
    Two things occur to me about the length of an island.

    The definition is clever, but seems to fail on the example you give of a ring shaped island. Your algorithm would result in only half of the 'true' length. For example, if the circumference is 100 miles, then the shortest longest distance between points would be 50 miles. Making a small break in the ring would double the length of the island.

    The second point is that, if I am not mistaken, this is basically the mathematical concept of Limit Superior (lowest highest number) or Limit Inferior (highest lowest number) (http://en.wikipedia.org/wiki/Limit_superior_and_limit_inferior). Maybe you could submit your example to brighten up the rather dry matehmatical description. On the other hand, I could be wrong about this.

    Phil

  • Anonymous
    December 16, 2004
    > Making a small break in the ring would double the length of the island.

    Yes, it would. It would double the longest shortest distance between two points. A long, skinny island bent into a near-circle is LONGER than a long, skinny island squashed into a circle with a lake stuck in the middle.

    You're describing a desirable property of the length metric, not an undesirable property.

    > this is basically the mathematical concept of Limit Superior

    Yes, you are absolutely right. The existence of a shortest path depends on the Axiom of Continuity, which states that bounded sets of numbers have superior and inferior limits, and thereby defines the real numbers.

  • Anonymous
    December 16, 2004
    > Whidbey Island's real claim to fame is that
    > it is the longest island in the United
    > States that is also in the Pacific Ocean but
    > not part of Alaska or Hawaii -- big whoop.

    Well if it's longer than Guam then it's a moderately big whoop. (I think the "if" in that statement is longer though.)

  • Anonymous
    December 16, 2004
    I would have thought that the length of an island is the length of the longest side of the smallest rectangle which bounds the island. But perhaps not.

  • Anonymous
    December 16, 2004
    Go to www.SpiralJetty.org.

    Suppose that we detached Spiral Jetty from the mainland, making it an artificial island in the Great Salt Lake.

    If we say that the length of Spiral Jetty is the length of the longest side of the smallest rectangle, we'd get a value FAR shorter than the 1500 feet it takes to walk from one end of the spiral to the other.

    "Longest side of smallest rectangle" -- where by "smallest" you mean "the rectangle with the smallest longest side", not "the rectangle with the least area" -- works well for islands that are everywhere convex. It underestimates concave islands.

  • Anonymous
    December 17, 2004
    The comment has been removed

  • Anonymous
    December 17, 2004
    Sure, it would be madness IF I WERE A CROW. Crows can travel through the three-dimensional manifold that is the Earth's lower atmosphere.

    I, being a human, tend to WALK from place to place on the two-dimensional manifold that is the solid surface of the earth. The question of how long something is therefore has to do with the farthest I could possibly have to walk.

  • Anonymous
    December 17, 2004
    Ryan Island is the largest island in the largest lake on the largest island in the largest (freshwater?) lake (Superior).

    Treasure Island is the largest island in a lake on an island in a lake (Huron).

    Very important distinctions, especially for people talking about longest shortest shortest paths.

  • Anonymous
    December 18, 2004
    The comment has been removed

  • Anonymous
    December 20, 2004
    Nice arguments. Reminds me, though, of other arguments that spring basically from a simple concept (i.e. "longest") being applied where it is not applicable (i.e. "island"),i.e.:

    - The greenest pasture. Think about it, anyone owning a pasture will want to adopt a definition that makes his (hers?) the greenest. But, in reality, the claim of a pasture being the greenest, is meaningless. But no more so than the longest island.

    Although most people can understand what is probably meant by these things, that is more an indication of our abilities with "fuzzy logic", than anything else. Humans have an innate ability to understand much that we are unable to define with exactitude. At the same time, we seem to have an affinity for trying to come up with an adequate definition for things that, owing to our aforesaid abilities, need no such thing.

  • Anonymous
    December 26, 2004
    How to measure an island of any shape. I'm NOT a mathematician, but surely the easiest way would be to imagine a circle which just touches two points on a real island's perimeter (i.e., not a circular one) and does not include any part of it. Is not the circle's diameter the maximum length of the island?
    Path lengths should have no bearing on the concept of overall length, even for 'bent' islands or islands with lakes in them.

  • Anonymous
    December 26, 2004
    The comment has been removed

  • Anonymous
    December 31, 2004
    The comment has been removed

  • Anonymous
    January 05, 2005
    The comment has been removed

  • Anonymous
    January 05, 2005
    The comment has been removed

  • Anonymous
    September 19, 2005
    Taking the third dimension into account introduces some issues concerning those mountains, though. When given two islands of identical outline, does it make sense that one would be longer than the other merely by reason of it having a taller mountain in the middle? I think not. It also occurs to me that, by your as-the-donkey-trundles path definition, an island can have it's length altered by means of digging a tunnel. We'd have to consider then if a record-holding island should loose it's status by dint of having a convenient highway tunnel, or even a bridge connecting two points. And what if the bridge is of the folding-up variety?

    The circular island with the lake in it's middle has similar problems. Given two islands of identical diameter, why should one be considered longer because it has a larger lake in the middle? If we were to install a hydroelectric project on an island, why should we consider it's length to have changed?

    To get around these issues, and other impediments like variations in the curvature of the earth (which unfairly impacts some big Canadian islands, I might add), we need some way of having that surface path ignore the intervening topography.

  • Anonymous
    April 28, 2006
    Long Island is longer no matter how you slice it.  However, the Supreme Court by a count of 9-0 declared Long Island to be a peninsula and not in fact a "true" island.  It looks like an island to me, but.....

  • Anonymous
    March 04, 2007
    What if the an almost complete ring shaped island is connected at one end by cave or tunnel, to an island that is a complete ring?

  • Anonymous
    October 25, 2009
    The comment has been removed