1. Highway problem
Given an arbitary point set S in the plane.
The question is how to place a highway line segment in the plane
so that the average traveltime will be minimized.
The traveltime between two points p und q without any highway
equals the Euclidian distance:
d(p,q):=|pq|
The highway-problem can also be considered for other metrics,
for instance Manhattan and maximum metric.
Both alternatives are implemented in the applet.
The highway can be used as fast connection between the points x and y with constant velocity v.
That means, you can travel from point x to point y in time |xy|/v.
On the other hand the highway can be an ostacle if it intersects the connection between the points p and q.
This can increase the traveltime between those points.
If the highway blocks pq, the traveltime with highway is definded as:
d_h(p,q) := min(|px|+|xy|/v+|yp|, |px|+|xq|, |py|+|yx|/v+|xp|, |py|+|yq|).
If the direct path from p to q is not blocked, we have:
d_h(p,q) := min(|pq|,|px|+|xy|/v+|yp|, |px|+|xq|, |py|+|yx|/v+|xp|, |py|+|yq|).
For any finite point set S the average traveltime is defined as:
daverage(S) := (Σp≠q:S∋p,q d_h(p,q))/binomial(|S|,2)
The applet allows several input modes.
Besides finite points sets you can choose between the input modes
"curve" and "curve interior".
In curve mode, the point set S consists of all points on the curve,
in curve-interior mode, S constists of all points which are located in the region enclosed by the curve.
In thise cases the average travel time is defined as an integral analogous to the sum above.
2. How to use the applet?
point input:
After clicking on the button point-input, you can insert points with the left
mouse button on the editable screen. If you are in the curve or in the curve
inside input mode, then you must finish the input by clicking the right mouse
button.
highway input:
Click on the highway input button.
Then you insert a highway by clicking on the two endpoints of the highway.
brute-force method:
After inserting a point set, the applet can compute approximately the optimal
highway. To do so, click on the calculate-highway button.
change highway speed:
At the beginning the highway speed is set to infinity.
If you want to consider a finite velocity v, you must
deselect the infinity checkbox and insert the desired speed value in the corresponding textfield.
Be sure to finish the input with ENTER.
calculate average traveltime:
After inserting a highway and a point set,
the average traveltime can be calulated by clicking on the calculate
traveltime button.
3. References:
Rainer Montignies, "Platzierung eines Highways", Diplomarbeit, Universität Bonn, 2007
4. Highway applet:
Start the Highway Applet (approximately 4 MB)