Author |
Topic: Road Layout (Read 1699 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Road Layout
« on: Jan 31st, 2003, 4:46am » |
 Quote  Modify
|
ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT ROAD LAYOUT
a) Discrete-Case
N cities are located at integer coordinates on a Cartesian grid. Your task is to lay down roads along the grid such that all the cities are connected, and the total amount of road you lay down is minimized. Devise an algorithm to solve this problem in general.
b) Continuous-Case
N cities are located at real coordinates on the Cartesian plane. Your task is to lay down roads such that all the cities are connected, and the total amount of road you lay down is minimized. Devise an algorithm to solve this problem in general.
c) N-Dimensional Case
N cities are located at real coordinates in an N-dimensional world. Your task is to lay down roads such that all the cities are connected, and the total amount of road you lay down is minimized. Devise an algorithm to solve this problem in general.
Note 1: (potentially unnecessary clarification) I use the modifier "connected" in the graph theory sense, meaning there exists a path from one city to any other city. In the Discrete-Case, when I say "along the grid", I mean that roads can only travel horizontally or vertically. A road network is comprised of line segments, and the endpoints of any line segment should lie on integer coordinates. Also, note that the problem does not restrict the endpoints of a line segment to the locations of the cities. So it will often be beneficial to invent intermediate points where roads should intersect. Finally, of course the more efficient your algorithm is, the better.
Note 2: Warning. Parts b) and c) may be intractable. My friend Yosen and I just made them up! And we're stuck on Part a) anyways!
Note 3: Problem adapted from topcoder.com, which featured the discrete-case. Quite an interesting and practical problem eh? I wonder if real road layout people think about these things.
|
| « Last Edit: Jan 31st, 2003, 5:27am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Road Layout
« Reply #1 on: Jan 31st, 2003, 5:25am » |
Quote Modify
|
Hidden below are a subset of our thoughts while working toward a solution in the Discrete-Case, the only case we've thought about so far. You might want to ponder about the puzzle a bit yourself before reading them; I often find it difficult to conceive original ways of looking at a problem after someone has shown me his or her perspective.
Intuitively we want to send non-diagonal roads from each city toward the interior of the convex hull, and we want to get the roads from each city to intersect as quickly as possible, so they can share road as the paths run toward the interior.
Note that when two roads intersect, that intersection point is like a new city. This observation may lend itself to a recursive solution.
I suggested laying out roads for the innermost cities and then expanding outwards. By innermost, I mean closest to the geometric center of the convex hull. Then we will update our road network as nearby outlying cities are added into consideration.
n=2 is a trivial case. But there are two possibilties for n=3: either two points or all three points fall on the rectangular convex hull. By rectangular convex hull, I mean I am restricting the shape of the convex hull to a rectangle.
(Pencil and paper might help to process the following paragraph.) We looked at the following coordinates for n=3: (0,0), (1,2), (2,1). We fire non-diagonal lines from each city toward the interior. Do some handwaving ... ehh ... and it's "obvious" that all roads should intersect at (1,1). However, note that (0,0) can get to (1,1) in two different ways: right one unit and up one unit, or up one unit and then right one unit. Which way we choose will affect whether we need to redo our roads when a 4th city is added. For instance, assume we choose right one unit and up one unit, such that there is road between (0,0) and (1,0), (1,0) to (1,2), and (1,1) to (2,1). Now if the 4th city is at (-1,0), we see that we should have chosen the other way to hook (0,0) to (1,1), because then the 4th city could have joined the network at (0,1).
Now consider the following four points: (0,0) (1,-1) (2,1) (1,2). Connect them optimally. There is no 5th point outside the convex hull of these points which could necessitate reconstruction. This is because there are no alternative layouts which satisfy the desired conditions.
This seems to be the crux of the problem: 1) characterizing conditions when multiple paths of equal distance exist, 2) characterizing conditions when adding a city could potentially cause reconstruction (if we were unlucky in any of our previous choices when there were multiple paths of equal distance).
Some notes on 1) and 2): Suppose you have just processed k cities, and now you are considering the (k+1)th city, moving outwards from the interior. If you fire a non-diagonal ray from the (k+1)th city toward the rectangular convex hull of the first k cities, then if that ray hits an existing city, no rewiring is necessary (2). However, if the ray never hits the convex hull, then there exist multiple paths to the nearest corner of the convex hull (1).
Perhaps a more elegant approach would recursively increment the number of cities under consideration regardless of whether they are relatively in the plane.
grrr i'm hungry
|
| « Last Edit: Jan 31st, 2003, 2:00pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Road Layout
« Reply #2 on: Jan 31st, 2003, 3:42pm » |
Quote Modify
|
Concerning the continuous case. This is actually a well-studied problem. I don't recall for sure, but I believe there is no algorithm for solving it in less than exponential time.
One thing I do know is that for any minimal solution all intersections will be three roads meeting at 120o angles. This is not hard to prove. If three roads meet at other than 120o, you can show that moving the intersection over a little will shorten the total road length. If more than 3 roads meet, breaking the intersection up into a series of such meetings also shortens the road length.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
visitor
Guest
|
I'm not a programmer, so you can probably ignore this, but maybe some of this will make sense.
For the discrete case, what if you start with the towns closest together. In the mappings where the town placement is not a smooth scattering, converging in the center may not be best; if, eg, you have a circular or crescent shaped scattering of towns. Perhaps divide the map into quadrants and sections, seeking areas of highest density of towns to optimize first.
Start with the two towns closest together. Instead of picking a path between any two towns, plot out a rectangular section of potential direct paths. Move on to the next closest pair, and keep going until all towns have been linked (including links between quadrants even if that involves some longer links). Several methods to begin optimizing: seek grids that overlap, measure the distance between non-intersecting grids within a quadrant, and where three or more grids come fairly close together, test the possibility of placing a crossroads at the center. Rate every grid on how certain you are that one route through the region is optimum and work your way from the surest to least sure grids.
This is by no means complete, but maybe some of these ideas can be meshed with your own ideas and programming experience.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Road Layout
« Reply #4 on: Feb 1st, 2003, 2:30pm » |
Quote Modify
|
on Jan 31st, 2003, 3:42pm, Icarus wrote:Concerning the continuous case. This is actually a well-studied problem. I don't recall for sure, but I believe there is no algorithm for solving it in less than exponential time.
One thing I do know is that for any minimal solution all intersections will be three roads meeting at 120o angles. |
|
I'm not sure why this is true. In the continuous case, consider the following scenario: cities at (0,0) (5,0) (0,5) (5,5). Then the best thing to do is pave roads along the diagonals of the square formed by these cities. This intersection has four roads meeting at 90 degree angles.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Road Layout
« Reply #5 on: Feb 1st, 2003, 2:58pm » |
Quote Modify
|
on Feb 1st, 2003, 2:30pm, william wu wrote:
I'm not sure why this is true. In the continuous case, consider the following scenario: cities at (0,0) (5,0) (0,5) (5,5). Then the best thing to do is pave roads along the diagonals of the square formed by these cities. This intersection has four roads meeting at 90 degree angles. |
|
According to my calculations, your way would take 14.14 units (2*sqrt(2*5^2)), while Icarus's way would take 13.66 units (there would be five ways, connecting in the square at points (1.44,2.5) and (3.55,2.5) -- 4*2*5/sqrt(12)+5-10/sqrt(12))
But I may be wrong.. 
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Road Layout
« Reply #7 on: Feb 1st, 2003, 7:16pm » |
Quote Modify
|
The continuous case can also be approached by experimental means. Set up a map on a board and place pegs at the location of each town. Place a second thin board on top to form a "peg sandwich". Dip the contraption in a good bubble solution an after when you pull it out, cut holes in the thin board to allow any trapped air to escape. The remaining bubble film between the pegs should follow the lines of a road system that is a local minimum (that is, small variations will all be longer, but it is possible that a major variation would be shorter).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Road Layout
« Reply #8 on: Feb 2nd, 2003, 1:26am » |
Quote Modify
|
Fascinating. A friend who did graduate research on bubble surfaces told me what the problem is officially called: the discrete case is called the Rectilinear Steiner Tree problem, and the continuous case is the Euclidean Steiner Tree problem. Formally, you are given a weighted graph in which a subset of the vertices are identified as terminals, and you want to find a minimum-weight connected subgraph that includes all terminals. In general, finding a Steiner Tree is NP-hard.
Some real world scenarios in which this problem arises include electrical wiring, water piping, ventilation ducts, land surveying, and phylogenetic trees.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Road Layout
« Reply #9 on: Feb 3rd, 2003, 5:20pm » |
Quote Modify
|
What's interesting is that, if you require that intersections can only occur at pre-existing cities, the problem suddenly becomes very simple (order N2, or better).
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Road Layout
« Reply #11 on: Mar 7th, 2003, 7:54pm » |
Quote Modify
|
SWF has pointed out on another thread that the 120o rule for the continuous case has exceptions. For example, if all the cities lie in a straight line. We can put some bends in the line as well, as long as the angles > 120o.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Road Layout
« Reply #12 on: Mar 11th, 2003, 11:07pm » |
Quote Modify
|
How about this, then? All intersections at points other than cities must be three roads at 120 degrees each.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove