Tagged: Voronoi Diagrams Toggle Comment Threads | Keyboard Shortcuts

  • Joseph Nebus 6:00 pm on Tuesday, 17 January, 2017 Permalink | Reply
    Tags: capitals, , , , Voronoi Diagrams   

    48 Altered States 


    I saw this intriguing map produced by Brian Brettschneider.

    He made it on and for Twitter, as best I can determine. I found it from a stray post in Usenet newsgroup soc.history.what-if, dedicated to ways history could have gone otherwise. It also covers ways that it could not possibly have gone otherwise but would be interesting to see happen. Very different United States state boundaries are part of the latter set of things.

    The location of these boundaries is described in English and so comes out a little confusing. It’s hard to make concise. Every point in, say, this alternate Missouri is closer to Missouri’s capital of … uhm … Missouri City than it is to any other state’s capital. And the same for all the other states. All you kind readers who made it through my recent A To Z know a technical term for this. This is a Voronoi Diagram. It uses as its basis points the capitals of the (contiguous) United States.

    It’s an amusing map. I mean amusing to people who can attach concepts like amusement to maps. It’d probably be a good one to use if someone needed to make a Risk-style grand strategy game map and didn’t want to be to beholden to the actual map.

    No state comes out unchanged, although a few don’t come out too bad. Maine is nearly unchanged. Michigan isn’t changed beyond recognition. Florida gets a little weirder but if you showed someone this alternate shape they’d recognize the original. No such luck with alternate Tennessee or alternate Wyoming.

    The connectivity between states changes a little. California and Arizona lose their border. Washington and Montana gain one; similarly, Vermont and Maine suddenly become neighbors. The “Four Corners” spot where Utah, Colorado, New Mexico, and Arizona converge is gone. Two new ones look like they appear, between New Hampshire, Massachusetts, Rhode Island, and Connecticut; and between Pennsylvania, Maryland, Virginia, and West Virginia. I would be stunned if that weren’t just because we can’t zoom far enough in on the map to see they’re actually a pair of nearby three-way junctions.

    I’m impressed by the number of borders that are nearly intact, like those of Missouri or Washington. After all, many actual state boundaries are geographic features like rivers that a Voronoi Diagram doesn’t notice. How could Ohio come out looking anything like Ohio?

    The reason comes to historical subtleties. At least once you get past the original 13 states, basically the east coast of the United States. The boundaries of those states were set by colonial charters, with boundaries set based on little or ambiguous information about what the local terrain was actually like, and drawn to reward or punish court factions and favorites. Never mind the original thirteen (plus Maine and Vermont, which we might as well consider part of the original thirteen).

    After that, though, the United States started drawing state boundaries and had some method to it all. Generally a chunk of territory would be split into territories and later states that would be roughly rectangular, so far as practical, and roughly similar in size to the other states carved of the same area. So for example Missouri and Alabama are roughly similar to Georgia in size and even shape. Louisiana, Arkansas, and Missouri are about equal in north-south span and loosely similar east-to-west. Kansas, Nebraska, South Dakota, and North Dakota aren’t too different in their north-to-south or east-to-west spans.

    There’s exceptions, for reasons tied to the complexities of history. California and Texas get peculiar shapes because they could. Michigan has an upper peninsula for quirky reasons that some friend of mine on Twitter discovers every three weeks or so. But the rough guide is that states look a lot more similar to one another than you’d think from a quick look. Mark Stein’s How The States Got Their Shapes is an endlessly fascinating text explaining this all.

    If there is a loose logic to state boundaries, though, what about state capitals? Those are more quirky. One starts to see the patterns when considering questions like “why put California’s capital in Sacramento instead of, like, San Francisco?” or “Why Saint Joseph instead Saint Louis or Kansas City?” There is no universal guide, but there are some trends. Generally states end up putting their capitals in a city that’s relatively central, at least to the major population centers around the time of statehood. And, generally, not in one of the state’s big commercial or industrial centers. The desire to be geographically central is easy to understand. No fair making citizens trudge that far if they have business in the capital. Avoiding the (pardon) first tier of cities has subtler politics to it; it’s an attempt to get the government somewhere at least a little inconvenient to the money powers.

    There’s exceptions, of course. Boston is the obviously important city in Massachusetts, Salt Lake City the place of interest for Utah, Denver the equivalent for Colorado. Capitals relocated; Atlanta is Georgia’s eighth(?) I think since statehood. Sometimes they were weirder. Until 1854 Rhode Island rotated between five cities, to the surprise of people trying to name a third city in Rhode Island. New Jersey settled on Trenton as compromise between the East and West Jersey capitals of Perth Amboy and Burlington. But if you look for a city that’s fairly central but not the biggest in the state you get to the capital pretty often.

    So these are historical and cultural factors which combine to make a Voronoi Diagram map of the United States strange, but not impossibly strange, compared to what has really happened. Things are rarely so arbitrary as they seem at first.

     
    • Matthew Wright 6:49 pm on Tuesday, 17 January, 2017 Permalink | Reply

      New Zealand’s provincial borders were devised at much the same time as the midwestern and western US and in much the same way. Some guy with a map that only vaguely showed rivers, and a ruler. Well, when I say ‘some guy’ I mean George Grey, Edward Eyre and their factotum, Alfred Domett among only a handful of others. Early colonial New Zealand was like that. The civil service consisted of about three people (all of them Domett) and because the franchise system meant some voting districts might have as few as 25 electors, anybody had at least a 50/50 chance of becoming Prime Minister.

      Like

      • Joseph Nebus 3:45 pm on Saturday, 21 January, 2017 Permalink | Reply

        I am intrigued and delighted to learn this! For all that I do love maps and seeing how borders evolve over time I’m stronger on United States and Canadian province borders; they’re just what was easily available when I grew up. (Well, and European boundaries, but I don’t think there’s a single one of them that’s based on anything more than “this is where the armies stood on V-E Day”.)

        Would you have a recommendation on a pop history of New Zealand for someone who knows only, mostly, that I guess confederation with Australia was mooted in 1900 but refused since the islands are actually closer to the Scilly Isles than they are Canberra for crying out loud?

        Liked by 1 person

    • Matthew Wright 8:43 pm on Saturday, 21 January, 2017 Permalink | Reply

      Europe has had so many boundary changes since Roman times that I wouldn’t be surprised if there’s a tradition for governments to issue people with an eraser and pot of paint to update their maps – and, no question, their history IS the history of those boundary changes. Certainly it explains their wars…

      On matters NZ, I wrote just such a book – it was first published in 2004 and has been through a couple of editions (I updated it in 2012). My publishers, Bateman, put it up on Kindle:

      It’s ‘publisher priced’ but I’d thoroughly recommend it! :-) The parallels between NZ’s settler period and the US ‘midwestern’ expansion through to California at the same time are direct.

      The reasons why NZ never joined Australia in 1900 have been endlessly debated and never answered but probably had something to do with the way NZ was socially re-identifying itself with Britain at the time. The British ignored the whole thing for defence/strategic purposes, deploying just one RN squadron to Sydney as the ‘mid point’ of Australasia. Sydney-siders liked it, but everybody from Perth to Wellington was annoyed. I wrote my thesis on the political outcome, way back when.

      Like

      • Joseph Nebus 6:19 am on Saturday, 28 January, 2017 Permalink | Reply

        Aw, thank you kindly! I’d thought you might have something suitable.

        The organizing of territory that white folks told themselves was unsettled is a process I find interesting, I suppose because I’ve always wondered about how one goes about establishing systems. I think it’s similar to my interest in how nations devastated by wars get stuff like trash collection and fire departments and regional power systems running again. The legal system for at least how the United States organized territory is made clear enough in public schools (at least to students who pay attention, like me), but it isn’t easy to find the parallel processes in other countries. Now and then I try reading about Canada and how two of every seven sections of land in (now) Quebec and Ontario was reserved to the church and then I pass out and by the time I wake up again they’re making infrastructure promises to Prince Edward Island.

        I’m not surprised that from the British side of things the organization of New Zealand and Australia amounted to a bit of afterthought and trusting things would work out all right. I have read a fair bit (for an American) about the British Empire and it does feel like all that was ever thought about was India and the route to India and an ever-widening corridor of imagined weak spots on the route to India. The rest of the world was, pick some spot they had already, declare it “the Gibraltar of [ Geographic Region ]” and suppose there’d be a ship they could send there if they really had to.

        Like

  • Joseph Nebus 6:00 pm on Wednesday, 21 December, 2016 Permalink | Reply
    Tags: , compression, , Markov Chains, , , Voronoi Diagrams   

    The End 2016 Mathematics A To Z: Voronoi Diagram 


    This is one I never heard of before grad school. And not my first year in grad school either; I was pretty well past the point I should’ve been out of grad school before I remember hearing of it, somehow. I can’t explain that.

    Voronoi Diagram.

    Take a sheet of paper. Draw two dots on it. Anywhere you like. It’s your paper. But here’s the obvious thing: you can divide the paper into the parts of it that are nearer to the first, or that are nearer to the second. Yes, yes, I see you saying there’s also a line that’s exactly the same distance between the two and shouldn’t that be a third part? Fine, go ahead. We’ll be drawing that in anyway. But here we’ve got a piece of paper and two dots and this line dividing it into two chunks.

    Now drop in a third point. Now every point on your paper might be closer to the first, or closer to the second, or closer to the third. Or, yeah, it might be on an edge equidistant between two of those points. Maybe even equidistant to all three points. It’s not guaranteed there is such a “triple point”, but if you weren’t picking points to cause trouble there probably is. You get the page divided up into three regions that you say are coming together in a triangle before realizing that no, it’s a Y intersection. Or else the regions are three strips and they don’t come together at all.

    What if you have four points … You should get four regions. They might all come together in one grand intersection. Or they might come together at weird angles, two and three regions touching each other. You might get a weird one where there’s a triangle in the center and three regions that go off to the edge of the paper. Or all sorts of fun little abstract flag icons, maybe. It’s hard to say. If we had, say, 26 points all sorts of weird things could happen.

    These weird things are Voronoi Diagrams. They’re a partition of some surface. Usually it’s a plane or some well-behaved subset of the plane like a sheet of paper. The partitioning is into polygons. Exactly one of the points you start with is inside each of the polygons. And everything else inside that polygon is nearer to its one contained starting point than it is any other point. All you need for the diagram are your original points and the edges dividing spots between them. But the thing begs to be colored. Give in to it and you have your own, abstract, stained-glass window pattern. So I’m glad to give you some useful mathematics to play with.

    Voronoi diagrams turn up naturally whenever you want to divide up space by the shortest route to get something. Sometimes this is literally so. For example, a radio picking up two FM signals will switch to the stronger of the two. That’s what the superheterodyne does. If the two signals are transmitted with equal strength, then the receiver will pick up on whichever the nearer signal is. And unless the other mathematicians who’ve talked about this were just as misinformed, cell phones pick which signal tower to communicate with by which one has the stronger signal. If you could look at what tower your cell phone communicates with as you move around, you would produce a Voronoi diagram of cell phone towers in your area.

    Mathematicians hoping to get credit for a good thing may also bring up Dr John Snow’s famous halting of an 1854 cholera epidemic in London. He did this by tracking cholera outbreaks and measuring their proximity to public water pumps. He shut down the water pump at the center of the severest outbreak and the epidemic soon stopped. One could claim this as a triumph for Voronoi diagrams, although Snow can not have had this tool in mind. Georgy Voronoy (yes, the spelling isn’t consistent. Fashions in transliterating Eastern European names — Voronoy was Ukrainian and worked in Warsaw when Poland was part of the Russian Empire — have changed over the years) wasn’t even born until 1868. And it doesn’t require great mathematical insight to look for the things an infected population has in common. But mathematicians need some tales of heroism too. And it isn’t as though we’ve run out of epidemics with sources that need tracking down.

    Voronoi diagrams turned out to be useful in my own meager research. I needed to model the flow of a fluid over a whole planet, but could only do so with a modest number of points to represent the whole thing. Scattering points over the planet was easy enough. To represent the fluid over the whole planet as a collection of single values at a couple hundred points required this Voronoi-diagram type division. … Well, it used them anyway. I suppose there might have been other ways. But I’d just learned about them and was happy to find a reason to use them. Anyway, this is the sort of technique often used to turn information about a single point into approximate information about a region.

    (And I discover some amusing connections here. Voronoy’s thesis advisor was Andrey Markov, who’s the person being named by “Markov Chains”. You know those as those predictive-word things that are kind of amusing for a while. Markov Chains were part of the tool I used to scatter points over the whole planet. Also, Voronoy’s thesis was On A Generalization Of A Continuous Fraction, so, hi, Gaurish! … And one of Voronoy’s doctoral students was Wacław Sierpiński, famous for fractals and normal numbers.)

    Voronoi diagrams have a lot of beauty to them. Some of it is subtle. Take a point inside its polygon and look to a neighboring polygon. Where is the representative point inside that neighbor polygon? … There’s only one place it can be. It’s got to be exactly as far as the original point is from the edge between them, and it’s got to be on the direction perpendicular to the edge between them. It’s where you’d see the reflection of the original point if the border between them were a mirror. And that has to apply to all the polygons and their neighbors.

    From there it’s a short step to wondering: imagine you knew the edges. The mirrors. But you don’t know the original points. Could you figure out where the representative points must be to fit that diagram? … Or at least some points where they may be? This is the inverse problem, and it’s how I first encountered them. This inverse problem allows nice stuff like algorithm compression. Remember my description of the result of a Voronoi diagram being a stained glass window image? There’s no reason a stained glass image can’t be quite good, if we have enough points and enough gradations of color. And storing a bunch of points and the color for the region is probably less demanding than storing the color information for every point in the original image.

    If we want images. Many kinds of data turn out to work pretty much like pictures, set up right.

     
    • gaurish 5:10 am on Thursday, 22 December, 2016 Permalink | Reply

      I didn’t know that Voronoy’s thesis was on continued fractions :) Few months ago, I was delighted to see the application of Voronoi Diagram to find answer to this simple geometry problem about maximization: http://math.stackexchange.com/a/1812338/214604

      Like

      • Joseph Nebus 5:11 am on Thursday, 5 January, 2017 Permalink | Reply

        I did not know either, until I started writing the essay. I’m glad for the side bits of information I get in writing this sort of thing.

        And I’m delighted to see the problem. I didn’t think of Voronoi diagrams as a way to study maximization problems but obviously, yeah, they would be.

        Like

    • gaurish 5:04 am on Tuesday, 3 January, 2017 Permalink | Reply

      • Joseph Nebus 5:40 am on Thursday, 5 January, 2017 Permalink | Reply

        You are quite right; I do like that. And it even has a loose connection as it is to my original thesis and its work; part of the problem was getting points spread out uniformly on a plane without them spreading out infinitely far, that is, getting them to cluster according to some imposed preference. It wasn’t artistic except in the way abstract mathematics is a bit artistic.

        Liked by 1 person

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
%d bloggers like this: