3
$\begingroup$

Infinite Suburbia is a Euclidean plane, P. All residents live in open unit disks which, like caravans, can travel around but are stationary most of the time. When stationary, these disks lie in a fixed subset S ⊂ P which is a countable, disjoint union of open unit disks, as dense as possible in P, subject to the following caveat:

Residents of Infinite Suburbia like to travel. Therefore, if any disk d1 in S is currently vacant, any other disk d0 should be able to travel from its current stationary position, through the "road network" P\S (where, for the purpose of travelling, S is considered not to include d0 or d1), to the position of d1.

Furthermore, the manner of travel is constrained: associated with P is a (fixed) "differentiable" vector field, such that any point p ∈ P has an associated velocity v(p) (I guess by "differentiable" I mean that both of its components have a gradient). In particular, if p is the centre of a disk in S then v(p) = 0. If a disk is moving and its centre is currently at p, then it must travel with velocity v(p). Since v is "differentiable", it has a corresponding acceleration field, whose magnitude is bounded by A.

The city planners know that, being infinite, the Suburbia's residents are liable to want to travel arbitrarily far. Therefore, the main concern when originally deciding on S and v (apart from the density of S) was that expected journey times should be "asymptotically nice", in that if E(x) is the expected journey time between two disks which are no more than x distance apart (over all such ordered pairs in S), then E(x) should be asymptotically as small as possible. For variations on the problem, consider E to be the mean square journey time, or the maximum journey time.

The question, then, is: how to choose S and v? This will presumably be a balancing act since E(x) can be made much lower if S is sufficiently sparse. But I'm imagining a compromise looking like some sort of fractal, much like the road system in real cities, but much more ordered and extending to infinity. Assuming an exact optimum can't be found, what strategies will guarantee at least a decent approximation? Am I on the wrong track with the fractal idea? Is the problem, in fact, not sufficiently well-defined?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

I think the difficulty here is finding a non-arbitrary weighting for your two optimization conditions. As posed, one probably has a continuum of solutions with very little to commend one over the other.

Still there are some intriguing aspects of your problem which I would imagine, in the more interesting cases, are related to critical percolation in a $(3^6)$ lattice, which would indeed give a fractal.

But as it stands, we have a solution set containing a hexagonal disc packing at one end and a singleton embedded disc at the other.

Improve this answer
$\endgroup$
3
  • $\begingroup$ A plain hexagonal disk packing doesn't work, because there's no empty space for the disks to travel through. You need at least 1/3 of the space to be empty (a straight route can supply access to one row of disks on either side). What I'm wondering is whether something at least fairly close to this density can be attained with better behaviour for E. Even without weighting for the two conditions, investigating how they depend on each other could still prove interesting. Thanks for the link on percolation; this is an area of maths I'd never heard of before! $\endgroup$
    – Robin Saunders
    Commented Jul 15, 2010 at 9:26
  • $\begingroup$ The hexagonal disc packing is the limiting case where we do not care about traversibility at all and the singleton disc embedding is the other limiting case where we do not care about density. My point being that, until we set a weighting, we are probably stuck somewhere arbitrary between these two. But yeah, there may be interesting things we can say without a weighting- and if there are, I'd wager percolation theory would be the language for it. $\endgroup$
    – Tom Boardman
    Commented Jul 15, 2010 at 9:42
  • $\begingroup$ Here's my concern: I'm sure percolation theory will have much to say about going from a solid, non-traversible packing to an open, traversible one. But once we're restricting ourselves to choosing between the different traversible layouts, is it equipped to talk about optimizing such layouts for a hierarchical system of "streets, roads, highways" etc. where speed is taken into account? $\endgroup$
    – Robin Saunders
    Commented Jul 20, 2010 at 14:21
1
$\begingroup$

You might look for "branched transport". The idea would be to design the road network such that any, or almost any (in whatever sense) resident have an optimal transport plan available. For branched transport see for example this recent paper, or this one.

I suspect that the problem has no optimal solution due to rescaling (suppose that you got a optimal solution, then rescale the suburbia by 2 and replace all rescaled domains, which are now disks of radius 2, by 2 disks of radius one...).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .