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].

Tuesday, February 7, 2017

Points In A Circle Problem: Ruling Out Some Configurations

To date we've been using the term "edge triangle" to refer to a triangle of area 0.8286... that rests against two of the conjectured best obstacles O1, O2, and O3, as in this figure.


To generalize the term where helpful, let's say that given two distinct points P and Q, their edge triangle is the triangle whose base is the chord through P and Q, and whose third vertex lies on the disk boundary, maximally distant from the base.


(We won't apply the term when the chord is a diameter, in which case there are two points maximally distant from the base. We already know that in a minimal triple of obstacles, a diameter contains at most one obstacle; see item 6 here.)

The area of an edge triangle decreases as its base moves away from the disk center. This is clear from the figure: triangle E' is less wide and less tall than triangle E.


This could be restated as a constraint on minimal obstacles:

(*) Given three obstacle points X, Y, Z, if the chord through X and Y passes closer than a0/2 to the disk center—and if the edge triangle on that base doesn't strictly contain Z—then {X, Y, Z} is not a minimal set of obstacles.

This is because, under the stated conditions, a feasible triangle will exist with area greater than 0.8286..., making {X, Y, Z} worse than {O1, O2, O3}.

As an application, suppose three obstacle points X, Y, and Z all lie on a circle of radius a0, centered on the disk (as in the case of O1, O2, and O3) except that X, Y, and Z aren't equally spaced by 120° angles. Then it follows easily from (*) that the obstacles aren't minimal.


Proof: Because angles α, β, and γ aren't equal, at least one of the angles (say γ) exceeds 120°. Therefore the dashed distance in the diagram, a0 cos γ/2, is less than a0 cos 60° = a0/2. So if we draw the edge triangle whose base is the chord through X and Y, and whose third vertex is the projection from the center along the dashed line to the disk boundary, then this triangle will be feasible and will have area greater than 0.8286.... (This conclusion follows as long as X, Y, and Z lie on a circle of radius a0 or smaller.)

Here is one last result: if you displace one of the Oi, then the resulting obstacles are no longer minimal. In other words—keying on O1 for definiteness—we show that if the obstacles {X, O2, O3} are minimal, then X = O1


Proof: Let {X, O2, O3} be a minimal set of obstacles. We eliminate possibilities for X using the above diagram. (The three black dots in the diagram are the points O1, located at noon; O2, located at four o'clock; and O3, located at eight o'clock.)

First, X cannot be located on or below the diameter through O2, or else there would be no obstacle point above the diameter.

Likewise, X cannot be located on or below the diameter through O3.

Next, X cannot be located above chord EM. If X were located above chord EM, then spotlight triangle DEM could be enlarged to create a feasible triangle of greater area by sliding M upward along the disk boundary.

Likewise, X cannot be located above chord DL.

This, I believe, narrows down the possibilities for X to the two grey triangular regions (including the top boundaries, but excluding the bottom boundaries).


Now if X were anywhere in the dark triangle other than O1, then the chord through O3X would pass closer to the disk center than AB does; hence by (*), the edge triangle defined by O3 and X would be feasible and would have area greater than that of edge triangle ABC. And if X were anywhere in the light triangle other than O1, then the chord through O2X would pass closer to the disk center than GH does; hence by (*), the edge triangle defined by O2 and X would be feasible and would have area greater than that of edge triangle GHI.

The only possible location remaining for X is the location of O1, as claimed.



Intuitively, edge triangles penalize you for shrinking the obstacle triangle, while spotlight triangles penalize you for expanding it. This tradeoff was the intuition that led me to produce the Oi candidate triple in the first place. In the above reasoning, spotlight triangles helped to confine X to the triangular regions, and then edge triangles helped to drive X outward to O1.

Conclusion: In this post, we considered some classes of configurations that are, in a sense, "close to, but not quite" {O1, O2, O3}; and we showed that these configurations are not minimal.

***

I'm not sure if I ever mentioned this in previous posts, but in case not, I should say that the "Points In A Circle Problem" doesn't appear to be one that you can simply punt over to Mathematica for a solution. I tried it early on and I didn't get very good results, even in special cases. Maybe this shouldn't have been surprising: even if you specify the positions of the obstacle points, I think that finding the greatest area of a feasible triangle still isn't trivial for a computer. I believe you would classify this as a quadratically constrained quadratic program with a non-convex objective function—a class of problems that is NP-hard in general.

When I cast the problem for given obstacles as a constrained optimization over real variables and called Mathematica's Maximize and NMaximize commands on the system, I found inconsistent results. Sometimes the execution failed to return a result even after many hours; other times it threw some scary messages that made you wonder about the solution it eventually returned. These commands have some very intricate algorithms packed into them, and it isn't easy for a non-expert to know what they are doing under the hood. So I eventually stopped trying, and wrote my own solver and wrote custom code to do such things as generate combinatorial lists. If I'm being too pessimistic about Maximize and NMaximize, I invite correction from better Mathematica jockeys than me—or people for whom quadratically constrained quadratic programs are routine!