Friday, April 14, 2017

An Efficient Connector: The Solution And Some Additional Questions

Problem from the previous post:

Airport authorities would like to build a connector road (dashed line) so that maintenance vehicles can drive from one runway to the other without having to go all the way back to the airport terminal.

Given that the connector will be vertical, how far from the terminal should it be?

In my approach to the problem, I neglect the startup cost of building the connector road. My goal instead is to minimize the average distance that a maintenance vehicle would have to travel in order to get from the top runway to the bottom runway.

With the coordinates shown, the problem is to minimize, with respect to s, the value of the definite integral
\[ \frac{1}{c^2}\int_0^c{\int_0^c{\left(h + 2(b/c)s+ |x-s|+|y-s|\right)\,dxdy}}\,. \]
Before giving the result, let's make a couple of intuitive observations. First, if the two runways were parallel, then the optimal location for the connector would pretty clearly be at the midpoint. Second, since the runways aren't parallel, putting the connector at the far right looks worse than putting it at the far left…in both cases, the vehicles have to trundle the entire length of the runway to connect, but when the connector is at the far right, the vehicles also have to cover a long distance to get from one runway to the other. From these observations alone, we might expect the optimal location of the runway to lie to the left of the midpoint.

Evaluating the integral and minimizing the resulting function of s, we obtain

sbest = ½(cb).

This result shows how the parameter b pulls the optimal location leftward.


We could generalize this problem very far by asking something like the following: Given a closed, bounded, non-convex set L in a Euclidean space, find two points of L such that, if the two points are joined by a straight line segment, then the average distance between points in the set decreases by the greatest possible amount. In this form (if it is well posed), the problem might be difficult; even without the complication of identifying an optimal pair of points, just calculating the average distance between points in a convex set is apparently not easy. (This 2009 paper has some promising references if you're interested. Another relevant paper is this one from 2012.)

For the sake of having something to chew on, let's ask the following:

For the L-shaped set shown here (1 unit tall and 2 units wide), find two points of the L such that, if the two points are joined by a straight line segment, then the average distance between points in the set decreases by the greatest possible amount.

(Measure point-to-point distances along the segments; that is, all "travel" remains within the L and/or the connector.)

Note, in the problem as phrased here, when you calculate the average distance between points in the "after" picture, you must consider not only distances between points in the L, but also distances between points in the L and points in the connector, and between points in the connector and other points in the connector. Call this the homogeneous form of the problem (the connector becomes part of the network being analyzed, as opposed to its being thought of as made of different stuff or serving a different purpose). One could also consider the inhomogeneous form of the problem, in which the points of the connector aren't considered when calculating the average for the "after" picture. That's more like the runway problem.

I haven't done the problem in either the homogeneous or inhomogenous form; feel free to beat me to it!

I chose the L because it seemed like the easiest possible asymmetrical case. (Update 4/14: maybe an easier case would be a pair of parallel line segments of different lengths…but let's stick with the L.) One could try the problem for other non-convex sets, such as a polygon boundary, a circle, or some other plane curve. Two-dimensional sets could also be considered, such as two square regions given in position with respect to one another (a situation considered in this paper, though not with the goal of finding an efficient connector).


After you add a segment to a given set, you could repeat the problem with the resulting set, and so on. (If there were ever a choice between several equally good pairs of points, that would have to be handled somehow, either by choosing one of the pairs randomly or by choosing all of them at once.) I wonder what the limiting set looks like! Some kind of lacy fractal? And how well can one do, in the end? That is, given an initial network, does there exist an infimum value for the average distance between points attainable by adding connectors ad infinitum?

No comments: