An Optimized Road Network
Problem:
Consider a 2D region - it could be as simple as a square.
We are interested in laying out a network of roads (idealized as lines and polylines) in this region, satisfying the following requirements:
---------
0. The road network should be fully connected; there is one single network for the domain, no separate webs.
1. No point in the territory should be farther from the nearest point on *some* road by a given number 'a'. This is to ensure good penetration of the domain by the road network - no remote areas. Let us call 'a' the 'penetration constant'.
2. If A and B are two points which lie ON some roads in the network, and if we use the road network to travel from A to B, the total distance we move along the roads should not be more than the straight line distance from A to B by some given factor, say 'f' (*). This condition tries to ensure a minimum of 'intra-connectivity' in the network - it should be sufficiently cross-wired. Let us call 'f', the 'intra-connectivity factor'.
3. Yes; the road network should have the least possible total length.
---------
(*)Note: If A and B in the given region but not necessarily on the roads, we could follow the following protocol to reach B from A.
a) Find a road near to A and reach a suitable point on that road from A
b) Traverse the network of roads available optimally so that we reach B or very near B.
c) Leave the network and move to B.
A condition similar to #2 could perhaps be formulated in this case.
---------
The problem was inspired by the following question which opened the Landmark Pune Quiz 2007:
"Which Indian state has the largest length of surfaced roads?"
Update on April 5th 2007:
--------------------------
This is following some further thinking aided by a comment from Anurag.
1. It now appears that condition #3, the intra-connectivity requirement, should apply only for points on the network which are sufficiently far apart (their straight line separation should be greater than the penetration constant 'a' or 2*a). For points much less than 'a' apart, there can always be network distances 2* their straight line distance, (or sqrt(2)* straight distance) however dense the network is.
2. The road network can have open ends - especially near corners of the territory. This does not anyway spoil the connectivity.
3. It now appears that the penetration requirement can be achieved by forming *successive insets* of the boundary of the region - each successive inset is by twice the penetration distance 'a'. (Note: From the first inset of the boundary, we need to have open end roads running towards the vertices of the region until they reach a point distant a from the vertex) . Intuitively, it appears that these successive insets, suitably interconnected to ensure the intra-network connectivity would actually achieve the least lengthy network. The *suitable* interconnections might involve tricky details - but that these have to be between progressively and predictably shrinking polygons should simplify things.
Consider a 2D region - it could be as simple as a square.
We are interested in laying out a network of roads (idealized as lines and polylines) in this region, satisfying the following requirements:
---------
0. The road network should be fully connected; there is one single network for the domain, no separate webs.
1. No point in the territory should be farther from the nearest point on *some* road by a given number 'a'. This is to ensure good penetration of the domain by the road network - no remote areas. Let us call 'a' the 'penetration constant'.
2. If A and B are two points which lie ON some roads in the network, and if we use the road network to travel from A to B, the total distance we move along the roads should not be more than the straight line distance from A to B by some given factor, say 'f' (*). This condition tries to ensure a minimum of 'intra-connectivity' in the network - it should be sufficiently cross-wired. Let us call 'f', the 'intra-connectivity factor'.
3. Yes; the road network should have the least possible total length.
---------
(*)Note: If A and B in the given region but not necessarily on the roads, we could follow the following protocol to reach B from A.
a) Find a road near to A and reach a suitable point on that road from A
b) Traverse the network of roads available optimally so that we reach B or very near B.
c) Leave the network and move to B.
A condition similar to #2 could perhaps be formulated in this case.
---------
The problem was inspired by the following question which opened the Landmark Pune Quiz 2007:
"Which Indian state has the largest length of surfaced roads?"
Update on April 5th 2007:
--------------------------
This is following some further thinking aided by a comment from Anurag.
1. It now appears that condition #3, the intra-connectivity requirement, should apply only for points on the network which are sufficiently far apart (their straight line separation should be greater than the penetration constant 'a' or 2*a). For points much less than 'a' apart, there can always be network distances 2* their straight line distance, (or sqrt(2)* straight distance) however dense the network is.
2. The road network can have open ends - especially near corners of the territory. This does not anyway spoil the connectivity.
3. It now appears that the penetration requirement can be achieved by forming *successive insets* of the boundary of the region - each successive inset is by twice the penetration distance 'a'. (Note: From the first inset of the boundary, we need to have open end roads running towards the vertices of the region until they reach a point distant a from the vertex) . Intuitively, it appears that these successive insets, suitably interconnected to ensure the intra-network connectivity would actually achieve the least lengthy network. The *suitable* interconnections might involve tricky details - but that these have to be between progressively and predictably shrinking polygons should simplify things.
posted by R.Nandakumar @ 3:19 AM
3 comments
