Saturday, February 25, 2017

Points In A Circle Problem: Obstacles In A Minimal Set Can't Be Arbitrarily Close

A session last week on an elliptical machine gave an idea about minimal obstacles, and a red-eye flight last night gave me time to make some diagrams. So in this post, we'll show that the obstacles in a minimal set can't be too close to one another.

To that end suppose {X, Y, Z} is a minimal set of obstacles. For convenience, rotate the disk if necessary so that segment XY is horizontal (see the figure). Also, reflect if necessary so that segment XY lies in the upper half-disk. Then by previous work, obstacle Z must be located in the lower half-disk, at least a distance ½r0 from the disk center; and segment XY must be raised at least a distance ½r0 above the horizontal diameter of the disk.

(For reference, the diagram shows a circle of radius ½r0 centered at the disk center O. The diagram also shows a dashed triangle, the vertices of which are O1, O2, O3.)

If necessary, slide X toward Y reaching point X’ such that ZX’ is tangent to the circle. (X can't be to the Y side of X', because then segment ZX would approach closer than ½r0 to the center.) Likewise, if necessary slide Y toward X reaching point Y’ such that ZY’ is tangent to the circle. If segment X’Y’ is located above the circle, then draw segment X"Y" parallel to X’Y’ and tangent to the circle. Then segment X"Y" is no greater in length than segment XY (having been produced by two operations that either reduce length or leave it unchanged).

Now if point Z has coordinates (a, b), then the length of segment X"Y" can be found as  \[\frac{2r\sqrt{a^2+b^2-r^2}}{|b|-r} \equiv f(a, b)\,.\] To derive this, I required the system yb = m(xa), x2 + y2 = r2 to have a double root; this condition yields two slope values corresponding to the two tangents from Z. Using these slopes in yb = m(xa) with y = r then gives the x-coordinates of X" and Y". Subtracting the x-coordinates gives the expression shown above for f(a, b). (Some careful simplification is required along the way, but I felt like going this route instead of doing trigonometry.)

Knowing f(a, b) can help us to constrain the distance between obstacles in a minimal triple. Suppose we can specify a region of the disk that necessarily contains point Z. And suppose we can identify a number f* so that f(a, b) ≥ f* for all (a, b) in this region. Then we’ll have

Length of XY ≥ Length of X"Y" = f(a, b) ≥ f*

or in other words, the two obstacles X and Y must be at least f* apart. And since X and Y were chosen arbitrarily from the triple, the argument shows that in a minimal triple of obstacles, any two of the obstacles must be at least f* apart.

Let’s apply this argument to the next figure, which shows the entire unit disk, and which also shows two spotlight triangles on the same horizontal base. Observe that obstacle Z must belong to the (closed) shaded region—otherwise, by sliding point L or point M downward, we could create a feasible triangle with area greater than 0.828…. (Feasible because X and Y are located on or above the spotlight triangle's base.)

[[Note 2/27/17: I could have drawn the grey region smaller than I did, because point Z also has to be at least ½r0 below the horizontal diameter—otherwise we could draw a large feasible triangle below point Z. This doesn't change the conclusions below, but here is an improved figure.]]

The bottom corner of the shaded region has coordinates (0, −r0). It isn’t hard to show that f takes its minimum value there, f(0, −r0) = r0Sqrt[3] = 0.5559….  This configuration is shown in the next figure (improved analogously to the previous).

This gives our conclusion for today:

Any two obstacles in a minimal triple must be at least r0Sqrt[3] apart (0.5559…).

Note that the conjectured minimal obstacles {O1, O2, O3} do satisfy this condition—they form an equilateral triangle of side r0Sqrt[3].

No comments: