Today another in my fun-for-a-Friday series of reruns from the classic days of FAIC. This one was originally published in December of 2004. Enjoy!
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 the length
- if the island is “rounded” then the length is the longest distance to “opposite shores”
- if the island is “bent”, like Whidbey, then draw a bent line “down the middle” and measure its length.
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 a coral island in the form of a narrow ring. Say, an irregular pentagon with a 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. [1. If we formalized this statement, we’d have the mathematician’s definition of the diameter of a shape.]
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?
Photos are from Wikimedia Commons and all are in the public domain. Click on the images for photo credits and larger images.
Fabulous adventures in coding 
Doesn’t that go against the popular definition of length for a rectangular island? Assuming it’s 1mx3km, the length would be ~3km, but make it 1km wide and the length increases to roughly 3.16km, even though most people would still consider it to be 3km long.
Yes, it does.
Although the length of one of a rectangle’s longest sides is often a useful property, I’m not sure how usefully one could define a “length” property which was applicable to all shapes, which would match the length of a rectangle without a rectangle being a special case, and without causing very minor and topologically-insignificant changes in a shape to have major effects on the “length”. Forming a good definition for “width” which “naturally” matches a rectangle’s width isn’t too hard (e.g. the distance between the closest pair of parallel lines that would bracket the shape) but defining an unambiguous “length” consistent with that of a rectangle is harder. Using the worst-case parallel line distance would give a “length” measurement equal to a rectangle’s diagonal. Using a parallel-line distance that assumes the lines must be parallel to a side of the figure would mean that adding an infinitesimally-short side to a figure could greatly change the length. Measuring distance perpendicular to the “width” vector would fail in cases where many vectors would yield the same “width” [e.g. take a circle and replace a quarter of it with a square, yielding an “ice-cream-cone” shape; the width of that shape would be the diameter of the circle, but where should its length be measured and why?]
I’d posit that the only reason the “length” of a long and narrow rectangular island would be considered to be the length of the rectangle would be that the diagonal of a long and narrow rectangle is “close enough” that people don’t bother computing the diagonal.
I believe Treasure Island in Lake Mindemoya on Manitoulin Island in Lake Huron is the largest island in a lake that is on an island on a lake. I canoed around it once.
You got it!
That beats out my guess of the island in Lac Observation on the Louis-Babel Ecological Reserve island (which I personally call “PacMan Island” in Lac Manicouagan. http://goo.gl/maps/YOPru
At any rate, I think it’s the biggest island in a lake that has a lake that contains an island.
So according to you a bobby-pin shaped island would be really long? A serpentine or zig-zag shaped island could be imagined with an arbitrary length packed into a tiny area. Are you happy with that, or how are you going to rule that out? Some sort of rule about how wide the land has to be?
Nonsense.
A more reasonable measure is the furthest straight-line (or great circle for africa/europe/asia!) distance between any two points which are connected by land regardless of whether the straight line crosses water.
If the local tourist board want to use a different definition that is up to them.
Yes, a bobby-pin-shaped island is as long as it would be if “unfolded”, and an island can be arbitrarily long with a finite area. Just like a coastline can.
Think about it this way. Imagine you were running a footrace on the island where you get to choose the starting point and the finishing point (both on the shore) but the participants can choose the route (as long as they stay on the island). The length of the island is the length of the *longest* race course you can come up with, given that the participants will be maximally efficient in their choice of route. I think that’s a reasonable definition of length.
And a circular island is as long as it’s diameter, which could be shorter than a c-shaped island which could be contained within a circle of smaller diameter. Which is absurd.
As a matter of fact it’s not. I think you are confusing “longer” with “bigger”. They don’t have to necessarily mean the same thing.
I can take less time to arrive from A to B in a bigger island than I would in a smaller one. Last time I checked length was speed times time, so it seems reasonable to say that the smaller island is in fact longer.
Take for instance a 10×1 rectangle. Would you say it’s bigger than a 5×5 square? I wouldn’t, but it certainly is longer…
Your definition of length is commonly called “as the crow flies” length. Which is very useful for birds I’m sure, but less useful for me.
With your definition, take two islands, otherwise identical, but one has a bend in it, the bent one now got “shorter” as a result of its bend.
Nonsense.
Can anyone find the original paper referenced in Raymond Chen’s blog? None of the links the blog post have survived the passage of time.
The original research page is here: http://sitemason.vanderbilt.edu/page/hmbADS — I’ll update the post with a link.
Asked that as a quiz question once. Manitou Island! 😀
There does not have to be a shortest path between two points on the shore. If the shoreline isn’t well behaved there need only be a greatest lower bound in path lengths. Same thing goes for the longest of these. The explanation still works anyway if you replace “shortest” with “infimum,” and “longest” with “supremum,” so no a big deal.
Can you give an example of an island where the set of points on the island does not include its boundary?
All islands are compact. That’s an axiom of the isle space.
The boundary of the island is clearly in the water. You Lilliputians and your ridiculous notions!
There’s something rather delightful about mentally unpacking statements like “the longest shortest shortest path”.
While the longest shortest shortest path does a good job at identifying the optimal even distribution of poppyseeds. It doesn’t seem to translate well for determining how evenly distributed the poppyseeds are in a given configuration, it seems you really need something like the standard deviation among the shortest paths of the configuration as the measure of the evenness of the distribution in that configuration.
Hi Eric! As long as you’ve got your mathematician hat on, you’ve assumed that (a) your island is path-connected (for existence of the paths) and (b) that its geometry is closed (for existence of a minimal path).
Also, fun fact: islands in lakes on islands in lakes is a great test case for cartographic software data modeling. You can imagine naive modeling of land or water that would not render said islands correctly (or at all). I’ve seen it happen.
Correct. You’ll note also that I’m assuming that the boundary points of the island exist and are the relevant measure of length. If instead we considered the longest shortest path between any two points then the longest path might not end at the shore!
I don’t follow. By “boundary points exist” do you mean something fundamentally different than what I mean when I say “closed?”
Well, there are closed sets with empty boundary, right?
Its from 2004 so you were working on VS2005/.NET 2, aka Whidbey right ?
“There should be one unambiguous standard for length that doesn’t rely upon vague and imprecise notions…” I’m not too sure about that. IMO, there is a definition of length from the point of view of someone who has to walk/drive around the island where the longest shortest shortcut or whatever comes into play), and there is a definition of length (and width) from the viewpoint of someone who has to fit the island on a booklet for tourism ad, for example, or into the square on a map. In the latter case, the length of the containing rectangle is the way to go. WHat is it with the academians and the almost fantatical belief that there must be only one correct, tru answer? A bit like the dogmas of the Medieval Inquisition (no offence: just kidding 🙂 )
Wouldn’t the relative length of the island just be the ratio of the length of the perimeter of the island to its area? At one end you have a circle, and at the other, a line. That takes care of lakes as well, if you take the outer perimeter.
As for how to go from that relative measure of ‘length’ to the absolute length, I’m not sure!
If anyone wants to know what the mathematician hat looks like, it’s this one: http://www.tilley.com/The-T3-Cotton-Duck-Hat.aspx
An interesting (at least to me) consequence of your definition of “length” is that you can make an island longer by taking away a portion of its area. This is likely counterintuitive to most people’s conception of length. Also, how do you account for elevation in your definition? What if one point on the shoreline of the island is a sheer cliff rising several kilometers above the surface of the ocean? Does this contribute to the island’s length…or do we need to cartographically flatten the island (as it would appear on a map) even though to a runner (as in your example) this would indeed contribute to the distance they would have to travel.
A strange corner case is a “thin” ring island where part of the ring is only fractionally above sea level. At high-tide the ring would be broken and the island would instantly double in length. (Of course the shortest path at different times would depend on how deep you were willing to wade!) You could alternatively consider paths to be independent of tide (as I assume coastlines are defined now), but there is a still the unusual case where an insignificant change in topography can result in a drastic change in the defined length.
Perhaps better than asking “what is the length?” one should ask “why do you want a length?”. I imagine that different answers to “why” would reveal different ways to measure it. If running a race, for example, you have to consider a volcanic lava lake to be outside the boundary of “runnable area”. If the objective is to say “my island is bigger than yours” then just pick the method that makes your island sound bigger and then block your ears when anybody tries to tell you otherwise 😉
Pingback: Monads, part five | Fabulous adventures in coding