Finding the shore of a lake

Klaus Reinhardt Universität Tübingen, Germany, reinhard@informatik.uni-tuebingen.de

Abstract

We search for the shortest curve in the plane that does not fit inside some given polygon. This generalizes the “river shore” problem to the “lake shore” problem. We give solutions for several polygons including rectangles and all regular polygons and mainly focus on the triangle case, where we can give optimal solutions in some cases and approximative solutions in other cases.

1 Introduction

Imagine you wake up in a boat in some lake and there is thick fog so that you can not see further than ϵ. Although you know the shape of the lake, you do not know your position nor your orientation. So your goal is to row along a curve that is guaranteed to bring you to the shore at latest when you reach the end of the curve. Furthermore you want to use the shortest among these curves.

An equivalent problem is the longest worm for whom the lake is a comfortable quarter, that means which ever curve the worm wants to assume, he will find an orientation to do so within the lake.

The shortest curve will fit in the lake exactly in at least one orientation (else it could be shortened by ϵ) and will touch the shore on at least two sides (else it could be shifted away from the shore by ϵ, which means that you get already very close to the shore but do not notice it).

In [Bes65] the author proves that the minimum length of an arc that cannot be covered by an open regular triangle of side 1 is ≤ 0.98198.

In [AP89] and [CGLQ03] it is shown that the shortest curve in the plane that has unit width has length 2.2782...

In [Wet72] the author determines the largest number f such that every closed curve of length f can be accommodated in a given triangle. But in this paper we are interested in curves which are not closed, because there is no reason to return to the point where you woke up.

In this paper we first consider rectangles and parallelograms. For the triangle we use a Javaapplet available under http://www-fs.informatik.uni-tuebingen.de/ reinhard/ls.html , which executes the constructions in the paper and also allows to manipulate curves. In a lot of cases for a possible triangle we are confident that the construction gives the optimal solution, in other cases we think that we give good lower bounds for the solution.

2 The rectangle lake

Let without loss of generality the height be less than the width. Here we only distinguish between two cases: If the curve touches the shore at all 4 sides, then the shortest such curve is the diagonal. Otherwise if it only touches at 3 sides, it can be shifted away from one side by ϵ and thus the shortest such curve is the “yourt”-curve. The boarder case is if the length is \sqrt{(2.2782...)^{2} − 1} = 2.047... times the hight.

0.0 0.5 1.0 _{0.0  0.5  1.0  1.5  2.0} ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ................................................................  ................................................................ ................................................................................................................................................................................................................................ .....................................................................  .....................................................................

For longer rectangles the “yourt”-curve is optimal and for shorter rectangles the diagonal is optimal.

3 The parallelogram lake

Again we assume w.l.o.g. the horizontal lines to be longer than the sides. Here we have to consider the additional case, where the distance of the upper right corner to a point on the mirror of the left side at the bottom side is shorter than the diagonal and the yourt:

[figure]

The boarder case for all three possibilities is if the mirror of the left side is orthogonal to the diagonal, which is the case for an angle of 63.964...^{o}:

0.0 0.5 1.0 _{0.0  0.5  1.0  1.5  2.0} ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ...........................................  ........................................... ...................................................................................................................................................... ..............................................  ..............................................

A special case is the equilateral parallelogram with the angle of 60^{o}, where all curves which start and end orthogonal to a side and are reflected at two sides have the same length as the diagonal:

0.0 0.5 1.0 _{0.0  0.5  1.0  1.5  2.0} ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ .......................................................................................................................................................................................................................................................

We can apply the parallelogram case to the following general rule: Given a polygon with the property that a parallelogram containing the two most distant corners and having the property that the diagonal is the best solution, fits into the polygon then also the straight line between these point is the best solution.

From this we conclude that for any regular polygon the straight line between two most distant corners is the best solution as we demonstrate at the pentagon:

.................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

4 The triangle lake

Let without loss of generality the longest side have unit width and lie on the x-axis and furthermore the right side be the shortest. This limits the height h of the triangle to h ≤ \sqrt{3}/2 = 0.866.... Thus the upper point is in the following region:

0.0 0.5 _{0.0  0.5  1.0} ............................................................................................................................  ..................................................................................................................................................... . . . . . . . . . . . . . . . .

The first type of curve is a z-shape curve generalizing the curve in [Bes65]. It appears to be the best curve for h > 0.5 and is still a good candidate in some cases with h > 0.4. The idea of the curve is to have a point on both sides of the line from the start to the end point, which prevents the curve from lying flat along the bottom side. Arguments like rotation-symmetry and equal distribution of the slope suggest the following construction, for three lines of equal length:

0.0 0.2 0.4 0.6 _{0.0  0.2  0.4  0.6  0.8  1.0} .................................................................................................................................................................................................................................................................................................................................................................... .............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ............................................................................................................................................................................................................. ..........................................................................................................................................................................................................................................................................................................................................

We draw a line starting at (2/3, 0) having 3 times the slope of the left side. Then we draw the right line of the curve starting at (1, 0) orthogonally to this and continue the middle and the left line symmetriacly. As long as the length e of the left side is significantly smaller than 1, the curve can have no other orientation in the triangle. Otherwise we have to switch to the following construction:

0.0 0.2 0.4 0.6 _{0.0  0.2  0.4  0.6  0.8  1.0} .................................................................................................................................................................................................................................................................................................................................................................... ........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... .................................................................................................................................................................................................... .......................................................................................................................................................................................................................................................................................................................................... ..........................................................................................................................................................................................................................................................................................................................................

We draw a line starting at (1 − e, 0) using the angle at the top point. (This corresponds to the right side translated with a translation moving the left side to the bottom and (0, 0) to (1.0).) If the left end of the curve in the previous construction is right of this line, then we use the new intersection point instead and give the three lines of the curve tree times the slope of a line form (1.0) to this intersection point. When e gets even closer to 1, it is better to choose the other side:

0.0 0.1 0.2 0.3 0.4 0.5 _{0.0  0.2  0.4  0.6  0.8  1.0} .................................................................................................................................................................................................................................................................................................................................................................... ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ................................................................................................................................................................................... .....................................................................................................................................................................................................................................................................................................................................................................

In the case of an isosceles triangle with a h = 0.5 we find the worst triangle, where the curve has the length 0.996....

As we move down to almost isosceles triangles of lower hight, we found the following construction for good results:

0.0 0.2 0.4 _{0.0  0.2  0.4  0.6  0.8  1.0} ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ ..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ............................................................................................................................................... .................................................................................................................................................................................................................................................................................................................................................................... ...................................................................................................................................................................................................................................................................................................................................... ...............................................................................................................................................  .............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

Here we have to play with two very small parameters s_{1} and s_{2}. We start the curve with a line from a point (1 − l_{r} − s_{2}), where l_{r} is the length of the right side, to a point one the left side. The angle should be about 60^{o} (depending on s_{1}). Now we draw two translations of the triangle, which both move the top edge to the point (1 − l_{r} − s_{2}); one of them maps the short side of the triangle to the start line of the curve, the other makes the left side horizontal. Now we continue the curve going to the intersection of the two translated base lines and finally we end the curve at (1, 0).

For h < .2 and the right angle < 50^{o} the best solution we find is again the “yourt”-curve:

0.0 0.2 _{0.0  0.2  0.4  0.6  0.8  1.0} ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ................................  ................................ .................................................................................................................. ...................................  ...................................

For higher triangles we find an improvement by shortcutting the top-corner of the curve by making contact to the sides with two different points. We still keep the hight as the radius for the two arc segments having their center in the start resp. the end point of the curve.

0.0 0.2 _{0.0  0.2  0.4  0.6  0.8  1.0} .................................................................................................................................................................................................................................................................................................................................................................... ................................................................................................................................................................................................................................................................................................................................................................................................................................... .......................  ....................... ............................................................ ............................................. ............................................ ....................  ....................

We find the curve with the following construction: We mirror the triangle at its left side and another time at the short side. Then we place the start point of the curve such that its distance to the intersection of the base line of the triangle and the base line of the double mirrored triangle is the same as the endpoint in the double mirrored triangle to this intersection.

0.0 0.2 _{0.0  0.2  0.4  0.6  0.8  1.0} .................................................................................................................................................................................................................................................................................................................................................................... .......................................................................................................................................................................................................................................................................................................................................................................................................................... .......................  .............................................. ............................................................................................................................. ............................. ........................................... ........................  ................................................ .....................................................................................................  .......................................... .............................................................................................................................................................................. ..........................................  .....................................................................................................  ............................ ...........................  ...........................  ...........................

This means the line touching both circles has the same angle to both base lines. Furthermore we have to check that this line is left of the top of the triangle to make sure that the two mirrorings of the line correspond to the two reflections of the curve at the sides. If this should not be the case (as for the lower triangles), then we have to use the symmetric “yourt”-curve. Furthermore we have to check that the curve is not completely in the translation of the triangle where the top point is mapped to the start point of the curve and the left side to the base. Otherwise the have to force the reflection point at the right side to be the intersection with this translated base. If the distance of start point of the curve to the right side of the triable is less than h, then we can get better results by shifting the start point more to the left ....

For some cases of triangles with h between 0.3 and 0.5 (but not exclusive) we found good results with the following construction:

0.0 0.2 0.4 0.6 _{0.0  0.2  0.4  0.6  0.8  1.0} ........................................................................................................................................................................................................................................................................................................................................................................................................................................... ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. .................................................................................................................................................................................................................................................................................................................................................................. .........................................................................................................................................................................................................................................  ...........................................................................................................................................................................................................................................................................................................................................................................................................................................  ........................................................................................................................................................................................................................................................................................................................................................................................................................................... .............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

Again we have to play with two parameters. The first one determines the start of the curve. Then we draw the translation of the triangle where the top point is mapped to the start point of the curve and the left side to the base. We use the intersection of the translated base with the right side as point on the curve. The point of the curve at the left side could be determined by the reflection from the start point to the point on the right side but is many cases it is better move it more to the left, which is described by the second parameter. Then we draw the translation of the triangle where the base is mapped to the left line of the curve and the left side is mapped to the point of the curve at the right side. This gives us the end point of the curve. We conjecture that this construction is not optimal; better would be a variation, where the left line of the curve is slightly bent. This part of the curve would be not circular either.

For almost isosceles triangles of that height, we have to give up the construction of the point of the curve on the right side and instead use a symmetric version of the last translation. This gives us curves in the following three orientations:

0.0 0.2 0.4 _{0.0 0.2 0.4 0.6 0.8 1.0} ................................................................................................................................................................................................................................................................................................................................................................................ .......................................................................................................................................................................................................................................................

0.0 0.2 0.4 _{0.0 0.2 0.4 0.6 0.8 1.0} ................................................................................................................................................................................................................................................................................................................................................................................ .......................................................................................................................................................................................................................................................

0.0 0.2 0.4 _{0.0 0.2 0.4 0.6 0.8 1.0} ................................................................................................................................................................................................................................................................................................................................................................................ .......................................................................................................................................................................................................................................................

Here again we expect in optimal solutions the left and the right line to be replaced by slightly bent curves:

0.0 0.2 _{0.0 0.2 0.4 0.6 0.8 1.0} ................................................................................................................................................................................................................................................................................................................................................ ............................................................................................................................................................................................................

0.0 0.2 _{0.0 0.2 0.4 0.6 0.8 1.0} ................................................................................................................................................................................................................................................................................................................................................ ............................................................................................................................................................................................................

0.0 0.2 _{0.0 0.2 0.4 0.6 0.8 1.0} ................................................................................................................................................................................................................................................................................................................................................ ............................................................................................................................................................................................................

0.0 0.2 _{0.0 0.2 0.4 0.6 0.8 1.0} ................................................................................................................................................................................................................................................................................................................................................ ............................................................................................................................................................................................................

Conclusion : If we measure the qotient of the length of the curve and the height of the triagle, it increases continuously from 1.134 for an equilateral triangle to 2.278 for flat trinagles.

5 Outlook

There are still constructions to discover, which beat the constructions given here at a lot of cases. A far goal could be an algorithm, which works for all convex polygons. The general case of polygons looks hopeless as this would already be equivalent to a problem on “multilakes”, where you do not know in which of the lakes you are.

References

[AP89] A. Adhikari, J. Pitman. The shortest planar arc of width 1. Amer. Math. Monthly 96, pages 309–327, 1989.

[Bes65] A.S. Besicovitch. On arcs that cannot be covered by an open equilateral triangle of side 1. Math Gazette 49, pages 286–288,1965.

[CGLQ03] T. Chan, A. Golynski, A. Lopez-Oriz, C. Quimper. Curves of width one and the river shore problem. Proc. 15th CCCG, pages 73– 75, 2003.

[Wet72] J. E. Wetzel. On Moser’s problem of accommodating closed curves in triangles. Elem. Math. 27, pages 35–36. , 1972.