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:
At 9:26 PM,
Anurag said…
OK, requirements 0 and 1 can be satisfied by dividing the region into a Voronoi graph. However, additional points will have to be inserted in the graph to fulfill your requirement that no point in the region should be away from a road by more than a specified distance. Now, the Voronoi graph completely depends on the input set of points, so if you introduce additional point in an inefficient manner, the resulting graph will not satify condition 3.
At 7:17 AM,
R.Nandakumar said…
thanks anurag, for being the first visitor to this blog and for your interest.
if i get you right, the problem is now how to put those points in the region as seeds for a voronoi graph.
hope the conditions 0-3 capture all that is required of a good road network.
i guess one can think of a special case: a square region of say 10+ sqrt(2) units side. the minimum distance from any point to the nearest road is say 1 unit; the ratio f is say sqrt (2). now what is the network with least total road length?
one can readily think of a square grid with 4 corners each pulled in from the corners of the input square by 1 unit diagonally and every 'cell' having side 2 units? note that the side of the square region is given as 10 + sqrt(2) to allow forming such a square grid.
but, i am not sure if this square grid makes for the best road network. only very few points in the region are as far away from the roads as is allowed - the corners of the region and the mid points of the squares in the grid. so, it might just be the case that the network has greater penetration of the region than there really needs to be. it satisfies the sqrt(2) factor but then again, there are only very few points on the road grid that are boundary cases - eg: two diagonally opposite corners of the grid.
at least to me, even this special case is not obvious.
At 5:25 AM,
R.Nandakumar said…
i have a doubt regarding the voronoi graph idea - the best network could have roads with dead ends (the roads are two way roads and can be entered anywhere and their network is single connected unit) - this feature of possible dead ends might not be captured by voronoi graphs; not sure though.
a further thought: it appears that for *any* network in 2D, the ratio f (in the problem statement) cannot be less than sqrt(2). any attempt to increase cross connections to reduce the ratio below sqrt(2) seems to fail.
however the other condition that no point in the region be not more than a distance 'd' from the nearest road might allow a workaround - by introducing cross connections in a way so that all point pairs on the roads which are (sqrt(2)* their straight distance) apart lie within a distance d of each other (and thus we need not use the road network to go between them) and all other pairs of points on the network are more closely connected, thus achieving a value of 'f' less than sqrt(2).
Post a Comment
<< Home