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!

No comments: