2
$\begingroup$

Let's say I have a geographic map, a connected region divided into sub-regions. Is it possible to deform the map (the borders of the regions) so that each sub-region is of arbitrary area while maintaining the adjacencies?

I think it is possible, but I've forgotten almost all my topology. Is this a theorem? (Or basic definition?) Also, what is the correct way to describe how the original map and its deformation are related, does "homeomorphic" apply here?

  • 0
    Are the borders between regions line segments, piecewise linear curves, or smooth curves? The distinction between the latter two doesn't matter, and there is a nice constructive proof of existence, but if between two three-region junctions the border must be a single line segment, I think it becomes much harder.2012-05-30
  • 0
    @Rahul "Constructive proof of existence" is a nice hint :-). People tend to be interested in "regions" that can be represented with piecewise linear boundaries of finitely many segments, because that is what most GIS software supports. Although the regions need not be connected or simply-connected, you will have no problem accommodating that generality.2012-05-30
  • 0
    And I'm fine with smooth curves, definitely not restricted to line segments.2012-05-30
  • 0
    @whuber: Was it a hint? Does it suggest some well-known theorem that this is an obvious corollary of? If so, please post it as an answer, because I haven't actually studied any topology, and I just came up with an answer on my own.2012-05-30
  • 1
    @Rahul, shujaa: This is really a geometry problem, not a topology problem. To maintain piecewise smoothness of boundaries, it suffices to find a smooth area-preserving map from $\mathbb{R}^2-\{0,0\}$ to $\mathbb{R}^2-B(0,e)$ (a plane without a hole to a plane without a disk of radius $e$). By situating the origin within a region's interior, we effectively increase the region's area by $\pi e^2$ without changing any other areas. Repeated application does the job (use induction). Such a map is given in polar coordinates by $r\to\sqrt{e+r^2}$, $\theta\to\theta$.2012-05-30
  • 0
    @whuber: I don't see why that comment is a comment and not an answer.2012-05-30
  • 0
    @Rahul Too sketchy--I wrote it because it's the kind of thing I thought you were suggesting in your first comment :-).2012-05-30
  • 0
    @whuber, it's no sketchier than my answer :) Honestly, though, your comment seems pretty concrete to me. You just have to scale the figure down uniformly first so that you only need to expand regions, never contract them.2012-05-30

2 Answers 2

1

Here is a constructive proof that it is possible. It produces some pretty skinny and twisty regions that look like plasticene, though; @whuber's alternative solution in the comments will produce round blobbly regions that look like bubbles.

Enlarge the map uniformly so that every region is at least as big as its desired area. Now you just need to shrink the regions while maintaining adjacency. Pick a region $R$ whose area needs to be reduced. Find a connected sequence of regions $R, R_1, R_2, \ldots, R_n$ such that $R_n$ has a boundary with the outside space. Shrink $R$ to its desired area by "pulling in" its border with $R_1$ while keeping the endpoints of the border fixed, so that the topological adjacencies between regions do not change as shown below. This has increased the area of $R_1$, so for $i = 1, 2, \ldots, n$, restore $R_i$ to its original area by pulling in its border with $R_{i+1}$, or with the outside when $i=n$, in the same way. Thus you can reduce the area of any chosen region $R$ without changing the areas of the other regions, nor the adjacencies between regions. Repeat for all the regions that need shrinking, and you're done.

Below, for example, we reduce the area of region $A$ using the sequence $A, B$.

enter image description here

  • 0
    That part about "pulling it inwards" is a little hand-wavy :-).2012-05-30
  • 0
    @whuber: I agree, but is it not clear that between keeping the border segment as-is (not changing the area) and having it double back along the rest of the border of the region (making the area zero), there is an intermediate curve that attains any desired area less than the original?2012-05-30
  • 0
    No, mainly because I don't have a clear picture of exactly what you're doing. (Please note I'm not disputing the correctness of your solution; I just am unsure exactly what it is!)2012-05-30
  • 0
    @whuber: Ah, yes, this is the sort of thing that requires a picture. I'll post one soon.2012-05-30
  • 0
    @whuber: I've added one now. I still think you should post an answer of your own.2012-05-30
  • 1
    Nice diagram! Any idea on terminology? (I went back and bolded it in the question since neither answer addressed it yet.)2012-05-30
  • 0
    Lovely diagram! Concerning the algorithm: how do we know it terminates? Couldn't it cycle endlessly? E.g., if in your example region A were not part of the figure--creating an annulus--why wouldn't the algorithm "pour" C into B, D into C, E into D, and then B into E, creating a convoluted figure where the relative areas of B,C,D,E were no closer to the intended ratios than before?2012-05-30
  • 0
    @shujaa: *Homeomorphism* sounds all right to me, but I'm no expert so don't take my word for it.2012-05-30
  • 0
    @whuber: You're only allowed to move borders with regions you haven't visited yet. So if pathologically you poured C into B, D into C, and E into D, then when shrinking E you couldn't pour B into it; you'd have to pull in its border with empty space instead, and then you'd be done. More generally, this is why you have to start from the innermost region and work outwards. So that in the endgame when you come to a region whose neighbours you've all visited already, you still have its "coastline" to move freely.2012-05-30
  • 0
    Thanks, @Rahul. That brings up the next question. :-) What precisely does "innermost" mean and how do you know you can eventually work outwards? (Bear in mind that the regions need not be simply connected and that their union can be multiply connected, too.) I'm really not trying to give you a hard time here; it's merely that experience shows that an intuitively obvious algorithm can sometimes fail right at these extreme or exceptional cases, so care is needed to demonstrate correctness. (But maybe, on the other hand, I'm just being more obtuse than usual...)2012-05-30
  • 0
    @whuber: No, you're questions are completely fair. I had a clear and unambiguous algorithm in mind, but for ease of writing I glossed over some of the details; not a good strategy, evidently. :) But after thinking about your questions, I came up with a simpler procedure, so I've edited the answer. Please let me know if it's clear.2012-05-30
0

By intuition:

  • Imagine your map to have all regions with borders made of very elastic rubber
  • Shrink down your entire map to have all regions areas smaller than the smallest area you want
  • Start with a region and "blow" air into it to make it as big as you need. After that, make the region's borders rigid. This way if you deform another region of the map, the rigid region will maintain its area
  • One by one, continue with the other regions and do the same: expand and make it rigid

Links that may help: