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

Monday, April 24, 2017

Packing Books Into Boxes

As frequently as I've moved apartments in my life, I ought to be better than I am at packing up books. Taping down the flaps on a box, I'm apt to think: Might I have gotten more books in here if I'd done it differently? After so many years, why don't I have a system for this?

Apparently I'm not the only person who feels this way. Here's a moving company that offers advice for packing books—from the comments online, you can tell that book-packing vexes people.


"A constant puzzle with every box": that actually describes pretty well the abstract version of this problem, known as the three-dimensional bin-packing problem. A research article on the problem says that "The problem is strongly NP-hard and extremely difficult to solve in practice." Even the one-dimensional version of the problem is NP-hard.

To give a flavor of the subject, here's a snippet from the research article giving an approximate algorithm:


Right—why didn't I think of that?

For a much friendlier tour of the problem, click here.

I wonder if researchers have ever studied the book packing problem—that is, bin packing in the case where the bins are all 'book-shaped.' Conversely, perhaps the mathematicians who study bin packing might be able to learn something by talking to people who pack books for a living! Anyway here are a couple of videos for packing books. In common with some of the mathematical approaches I saw, both videos use strategies of pre-sorting the books and recursively creating layers. Check back the next time you need to pack up a library.





Saturday, April 22, 2017

An Efficient Connector: A Warmup Problem

(Updated below.) I haven't had much time to dig into the problem posed in my last post, that of adding an efficient connector to this L shape:



As a warmup however, I did calculate the average distance between points on the boundary of an equilateral triangle with unit side lengths (measuring distances along the boundary, as if the sides of the triangle were roads).



The average point-to-point distance is ¾, which is less than the length of a side. For details, see this two-pager.

***

Waking up fresh this morning, I think the mean distance is easy to calculate as follows. Once the first point is chosen, the second point is equally likely to be closer when measured clockwise or closer when measured counter-clockwise. If closer measured clockwise, all distances up to 3/2 are equally likely; if closer measured counter-clockwise, all distances up to 3/2 are equally likely. Therefore once the first point is chosen, all distances up to 3/2 are equally likely, and the mean distance is
\[\int_0^{\frac{3}{2}}{v\cdot\left(\frac{2}{3}\,dv\right)} = \frac{3}{4}\,.\]
This reasoning generalizes to any triangle if we replace 3/2 by the semiperimeter s:
\[{\rm mean\ distance} = \int_0^s{v\cdot\left(\frac{1}{s}\,dv\right)} = \frac{1}{2}s = \frac{1}{4}p\]
where p is the perimeter of the triangle.

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?

Monday, March 27, 2017

An Efficient Connector



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.

For example, with reference to the next figure, suppose that the vehicle is initially on the top runway, at the point indicated by the gray circle. To get to the indicated point on the bottom runway, the vehicle must drive along the magenta path to the other gray circle.


One way to begin the problem is to create a formula for the distance between a given initial location and a given final location. Then, one can use integration to average the distances over all initial and final locations. Because the average will depend on the location of the connector, the possibility arises of choosing the location of the connector that minimizes the average.

I did the problem for the dimensions shown:


In case anyone wants to solve it for themselves, I'll post my answer at a later time.

If you don't know calculus, you can try using your intuition to place the connector in an efficient location. Do you think that the most efficient connector will be halfway across, or less than halfway, or more than halfway?

Follow-up questions: Was it safe to assume that the most efficient connector is vertical? What if the runways are asymmetrical, as in this configuration?


Sunday, March 26, 2017

On Having A Favorite

To enroll in a frequent-flyer program online, I had to answer half a dozen security questions, including "What is your favorite kind of vacation?" and "What is your favorite cold-weather activity?" Who has ready answers to these kinds of questions?

"I like red the best!" says the toddler, as if his outfit didn't already make that clear. For grownups as well, having a favorite is for people who are at the toddler stage in their appreciation of something. I have a favorite bourbon, and that should tell you that I don't know much about bourbon. A good way to know that somebody isn't much of a reader is if they have a favorite book.

Now it is true that when I eat in a familiar restaurant, I almost always order the same thing. Always the pork curry at the Thai place in my neighborhood, always the chicken tikka at the Indian place. There's more to Indian food than chicken tikka, of course, but that's why God created other Indian restaurants. And if I didn't want a Shackburger and a strawberry shake, then I wouldn't be at Shake Shack, now would I?

This is not to say that Shake Shack hamburgers are the only hamburgers I like. I also like an occasional double quarter-pounder, or a "Mexican style" hamburger with Jack cheese, salsa, and avocado. Can't go wrong with a barbecue burger either—that bacon and zippy sauce!

Also, crumbled blue cheese is excellent on a thick hamburger.

Yet there are people out there who say things like, "My favorite hamburger is In-n-Out." Hearing this always makes me sad, not because I object to In-n-Out burgers in themselves, but because having a favorite hamburger just seems like a sad way to live.

To have a favorite X is to care too little about X's to arrange your life in such a way as to be surrounded only by wonderful X's. As few ties as I own, I can't say I have a favorite one. I like them all, or else why would I have them? Do you really want to put on a tie and think, "Eh, not my favorite"?

On the other hand, there are costs to not having a favorite. I can spend a long time in the morning choosing a tie to wear. A trip to the bookstore can take me hours and lead to no firm decisions; likewise for a trip to my Netflix queue. If nothing else, having favorites is efficient: a fact well known to parents of toddlers.

Saturday, March 25, 2017

Piece Out

Back for a few more notes on grammar and spelling:


1. Please know that the past tense of lead is led.

Wrong:
LeBron James lead the Cavaliers through a relatively stress-free fourth quarter on the way to the win. (Sports Daily, December 2016)
Fixed:
LeBron James led the Cavaliers through a relatively stress-free fourth quarter on the way to the win.


2. The preferred past tense of plead is pleaded.

Bad:
When arraigned Friday morning Goff plead not guilty and was assigned a public defender. Shortly before 1:30, through a second public defender, he plead guilty and was sentenced to 12 months in the Arkansas Department of Correction. (Booneville Democrat, March 2017)
Best:
When arraigned Friday morning Goff pleaded not guilty and was assigned a public defender. Shortly before 1:30, through a second public defender, he pleaded guilty and was sentenced to 12 months in the Arkansas Department of Correction.
My American Heritage Fourth Edition (2000) also lists pled as an acceptable spelling of the past tense.

Unfortunately, I see from the online version that the Fifth Edition now lists plead is an acceptable spelling of the past tense. My advice though is not to use that spelling. For one thing, it's inconsiderate writing—you'll trip up some fraction of your readers when they mistakenly read plead as present-tense the first time through.

I do think pled is fine, though according to the American Heritage entry linked above, the usage panel for the Fifth Edition prefers pleaded to pled by a wide margin.

And I see that the usage note doesn't even address plead as a past-tense spelling. I suspect that's because zero percent of the panel would find this spelling acceptable.

Although plead as a past-tense spelling is apparently widespread enough to be listed in the dictionary, I don't think it is used very often in high-status writing. Anecdotally, I find several thousand hits for a google search of "He pleaded guilty" on nytimes.com, but only about a hundred hits for "He pled guilty" or "He plead guilty." A quick scan suggests that the instances of "He plead guilty" tend to come from complicated constructions ("...it was required that he plead guilty...."), or from direct quotes of speech, or from internet comments.

Bottom line: use pleaded, or use pled if you prefer, but don't use plead because you might trip up your readers and/or come across like an internet commenter.


3. Don't hand-wave with around.

Lazy:
The committee developed a set of guidelines around ethics.
Better:
The committee developed a set of ethics guidelines for members.

The use of around, in the sense of the first sentence, is almost always a sign of vagueness. In the second sentence, we better serve the reader by stating more clearly what is going on—the guidelines are for members. Even if we don't give any additional information beyond the first sentence, we can cut out flab by writing
The committee developed a set of ethics guidelines.

Around, in the sense of the first sentence, is gaining currency. In addition to saving the writer the effort of being clear or concise, it appeals to those writers who worry that more common prepositions just don't sound smart enough.


4. Know your own verbal tics. Is piece one of them?

With the tic:
We haven't figured out the professional development piece.
Without:
We haven't figured out professional development.

Normally I don't comment on speech, just writing, but piece is a prominent verbal tic among knowledge workers. Their jobs require them to analyze systems into parts; it's natural to think of the parts as "pieces," and to speak accordingly. But I have yet to hear a sentence that wouldn't be improved by just not doing that.

Because it's unpretentious, I would even prefer
We haven't figured out the professional development thing.