Tuesday, April 25, 2017

An Efficient Connector: Solution For the L Shape

In this post I'll provide the solution to the problem I posed recently:



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. ...

Here's my result for the homogeneous problem, which I haven't checked thoroughly (details here):


The optimal connector attaches to the vertical about 63% of the way up, and it attaches to the horizontal about 36% of the way over. Adding this connector lowers the average distance between points by 12.8%.

To solve the problem, I generalized the dimensions of the L and derived a general expression D(abcde) for the average distance between points in the network.


(See the PDF for the actual expression.) Next I specialized to the problem at hand by expressing a, d, and e in terms of b and c. (For example, d = 2 − c.) The result was a messy function of two variables, D(b, c).

Complexity of the expression aside, the nature of the problem guarantees that the behavior of this function will be pretty simple, with just one basin to find. Here's a contour plot of D(b, c):


The minimum value D0 = 0.8719… occurs at (b0 = 0.3725…, c0 = 0.7186…).

Mathematica can express D0, b0, and c0 in exact form, but the expressions are lengthy; for example, D0 is the fifth real root of a certain 18th-degree polynomial whose constant term is

63,935,354,309,637,222,973,365,921,189,789,696.


That's it for the homogenous problem, although the foregoing should be thought of as provisional given my lack of stress-testing. 

By the way, having a general expression for D also makes it easy to solve cases where the L has a width:height ratio different from 2:1. For example, to analyze a square L, we can put d = 1 − c instead of d = 2 − c. Then the optimal connector looks like this:


The triangle in the upper-left corner has horizontal and vertical legs of equal lengths, about 0.364. The optimal connector for the square L decreases the average distance between points by about 15%.

Now if one wished to add another segment to decrease the average distance further….

No comments: