Sunday, April 30, 2017

In Honor Of William Wootters On The Occasion Of His Retirement

William Wootters, my earliest mentor in theoretical physics, will retire from Williams College this year. Wootters is a pioneer of quantum information theory: his groundbreaking paper "A single quantum cannot be cloned," coauthored with Wojciech Zurek in 1982, has been cited over 4,000 times.

Bill decided against having a Festschrift conference, so I won't be able to give a talk to celebrate his retirement. However, the alumni association invited Bill's former students to share reflections, and I wanted to share mine here as well.

***

The story of my physics career at Williams begins and ends with Bill Wootters. In my freshman year, Bill co-taught a course with Karen Kwitter about the major advances in physics and astrophysics during the 20th century. It wasn’t the typical starting point for physics majors, but for an under-prepared student like myself it was a perfect introduction to the subject. The fascinating course material, the lively teaching, and the professors’ abundant kindness all gave me courage to move ahead in the subject.

By the time of my senior year, I was completing my astrophysics major and writing an honors thesis in physics with Bill. It was a busy year for me, in some ways a tumultuous and overcommitted year. Bill’s kindness, charity, and steady professionalism kept my spirit calm and my mind on my tasks. Through his research supervision, Bill exposed me to new frontiers of physics and inculcated in me his own high standards for scholarship. He exemplifies the golden intersection of two of the most noble roles a person can have: on the one hand, scientist; on the other hand, educator.

When I arrived at Berkeley to study for a doctorate in physics, I couldn’t help noticing that my classmates who’d been undergraduates at large universities tended to know more than I did about particular topics—whether it be the Standard Model, or plasmas, or what have you. That first semester with its oral qualifying exams and its dozens of impressive classmates (Gino Segré! Nima Arkani-Hamed!) was once again an intimidating start. But I soon discovered that Williams had prepared me well. In truth, not all of my classmates understood the fundamentals as deeply as one needed to. I might not know everything, I often thought; but what I know I truly know. It was a gift to be given such a firm foundation on which to stand, and I thank Bill and the entire Williams physics faculty for that gift.

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?