Sunday, August 19, 2012

Ellipses and parking spots

Many times when going shopping, we find that we want to go to two different stores that are apart from each other, not far enough to drive to one place first and then to the other, and not close enough to be one next to the other.

When trapped in this situation, one gets into the predicament of 'where to park the car?'.

If we want to go to store A and store B, the idea is to park the car somewhere in between so we walk the least possible. Intuitively, parking right in the middle of the two stores is the best option, but a simple remark from Euclidean geometry tells us a different story.

Let us call the stores $A$ and $B$, and the car $C$ for simplicity. Hence what we want to minimize is $CA+AB+BC$, which is just $2AB$ if $C$ is in between $A$ and $B$, regardless of specific position of $C$. Therefore, it really doesn't matter where we park as long as it is in between $A$ and $B$.

If we consider the distance from the actual parking spot to the stores, we turn this into a planar problem

and again, our purpose is to minimize the distance $CA+AB+BC$, where now is the perimeter of a triangle with a fixed side

For this, a better approach is to consider the locus where the car gives a fixed total distance $CA+AB+BC$. This is a well known problem whose answer is nothing else but an ellipse whose major axis is $AB$.

Thus, In order to minimize the total distance that one would have to work, we have to look at all the parking spots inside the elliptical regions and find the one with smallest distance to the major axis, i.e., the closest parking spot that is in the middle of $A$ and $B$. Hence, as our intuition would tell, parking in the middle is the best strategy if we allow jaywalking in the parking lot.

If we want to be a little bit more 'rule follower' (pun intended) and we walk only in rectangular coordinates, the problem reduces to the one dimensional version of it and where we park actually wouldn't matter as long as it is between $A$ and $B$.

1. This comment has been removed by the author.

1. Generalice for n stores.
I think you have to find the poligon with minimal perimeter which has each store as a vertex (I suppose it's the convex one).
Then you can park anywhere on this perimeter

2. At least if there is a convex one. When there are no convex ones, then it is the most convex-like. haha. The one with minimal deviations from convexity. Perhaps there is a better way to find it.

2. If I want to minimize time instead of energy, I could park anywhere and finish shopping before you finish your measurements and calculations...unless there's an app for that ;)