13
$\begingroup$

Bose had fun touring the city of circular roads with Anita. Remember the rules? Every road is a circle and no sharp turns are allowed: at any transversal intersection, you continue going along the circle you are on, but at any tangential intersection, you may switch circles but maintain the direction (see the figure for a depiction of the rules).

depiction of the “no sharp turns” rules

Now it’s time for him to catch the flight back home. Unfortunately, Anita’s home (the red dot) and the airport (the blue dot) are on the opposite sides of the city and he doesn’t have much time.

the city with Anita’s home and the airport shown

Anita promises him to find the shortest route to the airport.

  • Can you help her, assuming the highways (the bigger, grey circles) are closed?
  • Is there a better route if the highways are open?

Clarifications:

  • Wherever the circles appear to be tangent, they are tangent.
  • The red (blue) dot is the left (right) most point of the circle it is on.
  • Assume constant speed.
Improve this question
$\endgroup$

3 Answers 3

Reset to default
16
$\begingroup$

First, consider a variation where we are allowed to u-turn at a tangent. All valid paths in the original problem are also valid in this variant, so if we cannot find a shorter path in the variant we also cannot find a shorter path in the original. In this variant it doesn't matter which direction you enter a junction from so the problem becomes a normal shortest distance problem.

Second, because each circle is only tangent at its four quadrant points, we can replace each circle with a diamond. All distances will be scaled down by a factor 2 sqrt(2)/pi; since all distances are affected equally that doesn't change which path is faster.

Now the map simply consists of a regular grid rotated by 45 degrees. The highways don't add any extra edges to the grid so they don't affect the result. The shortest path through a grid is the Manhattan distance.

The two points are 14 grid lengths (diagonal hops) apart. If each hop has a length of pi/4 as in F1Krazy's answer, then the shortest distance is 7pi/2. Because they were able to achieve this distance in the original problem by the above argument we know it to be the optimal solution in the original problem.

Added image:

OP’s image with part of the 45° rotated grid.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Exactly what I had in mind! Great job! I added an image to your answer to show a part of the grid. $\endgroup$ Commented Mar 3 at 18:56
  • $\begingroup$ Is your avatar showing a slide rule? I’ve always wanted one as a kid but they were out of fashion by then. $\endgroup$ Commented Mar 3 at 23:29
  • 2
    $\begingroup$ @Pranay Yes it is! I featured it in this answer. $\endgroup$ Commented Mar 4 at 16:31
  • $\begingroup$ Awesome! Does that mean you still have it (at least in 2022)? $\endgroup$ Commented Mar 4 at 16:49
  • $\begingroup$ A similar way to look at it without the grid: Whenever you take a quarter circle which brings you closer to your target in both dimensions (x and y) you are taking an optimal step. And you have to take three suboptimal steps (where you close distance in the x direction, but move away from your target in the y direction) - and this stays true no matter the route you take, because every quarter circle move always moves you the same amount in the x and y direction. $\endgroup$ Commented Mar 6 at 11:12
9
$\begingroup$

Let's say that the diameter of each small circle is 1 unit, such that the circumference of each small circle is π units and the circumference of each highway is 3π units.

Unless I'm missing something, the following routes are optimal:

enter image description here

Each route is 3.5π units long (or almost exactly 11 units).

With the highways open, the shortest route I can come up with is this:

enter image description here

Which also works out at 3.5π units long.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ I'm not sure how, but I'll have a think. $\endgroup$ Commented Mar 3 at 17:11
  • 2
    $\begingroup$ I used the free-hand drawing tool in Microsoft Powerpoint. Nothing fancy. $\endgroup$ Commented Mar 3 at 17:14
  • 3
    $\begingroup$ You could've taken another highway in the last one for an even more symmetrical solution! $\endgroup$ Commented Mar 4 at 1:48
  • 1
    $\begingroup$ @justhalf I didn't realise that until I'd already drawn it out, and decided not to bother redrawing since they come to the same distance anyway. $\endgroup$ Commented Mar 4 at 8:05
  • 1
    $\begingroup$ If we're optimizing for time rather than distance, one would assume you can drive faster on the highways, so taking that last stretch on the southern half of the southeastern highway ring would make the drive faster (if not any shorter in distance). $\endgroup$ Commented Mar 5 at 4:44
4
$\begingroup$

Another way to think about the highway problem:

All highway paths are equivalent to a route between A and B in the below figure as highways are tangent to roads at cardinal points.
enter image description here A to B on a highway is 1/4 the circumference of the large circles. We observe that the surface streets are also tangent at cardinal points so to go from A to B we require 3 * 1/4 the smaller circumference.

Since the small circles have 1/3 the highways' diameter they also have 1/3 the circumference and the two routes from A to B are equivalent.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 This was how I originally proved it. $\endgroup$ Commented Mar 4 at 19:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.