Sunday, December 11, 2016

Points In A Circle Problem: Summary To Date

The problem we've been considering is,
Place N points in the unit disk in such a way as to minimize the greatest possible area of a triangle in the disk that doesn't contain any of the points.
Note that the sense of 'containing a point' is strict: if a point lies on the boundary of a triangle, the triangle is not considered to contain the point. (Again I take the extrema to exist; this seems safe given the closed and bounded features of the problem.)

Here is a summary of where things stand:
  • For N = 1, placing the obstacle at the center of the disk results in a greatest feasible triangle area of 1. For any other location of the obstacle, there exists a feasible triangle of area greater than 1. Thus, the center of the disk is the unique solution to the N = 1 problem.
  • For N = 2, placing one obstacle at the center of the disk and the other obstacle anywhere in the disk results in a greatest feasible triangle area of 1. For any other arrangement of the obstacles, there exists a feasible triangle of area greater than or equal to 1. Thus, the center of the disk and an arbitrarily located second point together represent a solution (not unique) to the N = 2 problem. 
  • For N = 3, placing the three obstacles in the locations we have been denoting O1, O2, and O3 results in a greatest feasible triangle area of 0.8286369…. Our conjecture, not yet proven, is that no arrangement of three obstacles results in a smaller value than this for the greatest feasible triangle area.
A more economical way to summarize is to generalize the notation we used in the N = 2 solution. Given N obstacle points X1, …, XN in the closed unit disk, let

aN(X1, …, XN)

denote the greatest possible area of a triangle in the disk that doesn't contain any of the Xi. Let

aN* = minimum possible value of aN(X1, …, XN).

Then for each given value of N, our problem is to calculate aN* and find N points Xi* for which aN(X1*, …, XN*) = aN*.

Using this notation, our summary is:

  • a1* = 1 and a1(X) = 1 if and only if X = O, the center of the disk.
  • a2* = 1 and a2(X1, X2) = 1 if X1 = O or X2 = O.
  • a3* ≤ a3(O1, O2, O3) = 0.8286369….

It's been a lot of work for just a handful of equations! Still, getting to these results has been fun, and has required growing amounts of insight about the optimization. Some of this likely generalizes to arbitrary numbers of obstacles in arbitrary locations—such as the idea that if you know two vertices in a greatest-area feasible triangle, then the third vertex has to be one of a finite number of possibilities.

I will keep thinking about the N = 3 problem, although it's hard not to cheat and start exploring N = 4. Would any of my readers like to make a conjecture for the best obstacles in the N = 4 case? I'll stay out of the way while you work on it. Email any thoughts to zimblogzimblog@gmail.com.

***

A note about N = 3. The three obstacles O1, O2, and O3 are each a distance 0.32096… from the center of the disk. I have been using decimals and dot-dot-dot to express this distance, but it can also be expressed exactly as the real root of the cubic polynomial 5x3 − 4x2 + 7x − 2, namely


And the resulting greatest area (0.8286369…) can also be expressed exactly as the positive root of the polynomial 160000x6 − 265824x4 +  412857x2 − 209952, namely


To calculate these values, I first generalized the coordinates of O1, O2, and O3 to be functions of a variable radius r. Then I calculated the vertices of the spotlight triangle and the edge triangle in terms of r. Because the spotlight triangle and the edge triangle share a common base, the two triangles have equal areas when their altitudes are equal. The equal-altitude condition turns out to be equivalent to 5r3 − 4r2 + 7r − 2 = 0.

(Note, even Mathematica won't be able to solve the equal-altitude equation unless you are careful to orient your diagram so that the common base is horizontal. Doing so leads to much simpler expressions in r.)

7 comments:

Bill McCallum said...

Dammit Jason, I'm supposed to be working!

Jason Zimba said...

"Don't tempt me, Frodo!" https://drive.google.com/file/d/0B9YMTchBa3Y2RGQzYU5mNFVicDA/view?usp=sharing

Bill McCallum said...

L. M. A. O.

Bill McCallum said...

Seriously, this lead me to discover a formula for the area of a triangle inscribed in a circle of radius r, with vertex angles a, b, and c:

A = (r^2/2)(sin(a + b - c) + sin(a - b + c) + (sin -a + b +c))

I assume this is well-known to those who know it well, but I was not one of them.

Jason Zimba said...

That's cool! There is a lot to know.... (Reminds me, I had also never seen the "angle-side-angle" area formula 1/2(cot(A) + cot(B))^(-1)c^2 that I used in the Halloween Challenge post earlier this year.) Now since every triangle is inscribed in some circle, the "r" in your area formula is what I believe is called the circumradius of the triangle. I have seen some nice formulas for this in terms of the sides.

Bill McCallum said...

Here's another formula, which you can derive from that one. If u and v are the tangents of two of the vertex angles then

uv(u + v)
A = 2r^2 ----------------
(1 + u^2)(1+v^2)

Here you have to allow u or v = ∞ by taking limits. It u = ∞ then you have a right angled triangle sitting on the diameter of the circumscribed circle, and the formula gives 2r^2 v/(1+v^2). Fun exercise to check that is half the product of the two legs. If u and v are both infinity then the formula gives zero, which makes sense because a triangle with two right angles had zero area.

Bill McCallum said...

Well, that didn't come out too well. In linear format:

A = 2r^2 uv(u+v)/((1+u^2)(1+v^2))