PlaceNote 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.)Npoints 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.

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 O_{1}, O_{2}, and O_{3}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 X_{1}, …, X_{N}in the closed unit disk, let*a*

_{N}(X

_{1}, …, X

_{N})

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

_{i}. Let*a*

_{N}* = minimum possible value of

*a*

_{N}(X

_{1}, …, X

_{N}).

Then for each given value of

*N*, our problem is to calculate

*a*

_{N}* and find

*N*points X

_{i}* for which

*a*

_{N}(X

_{1}*, …, X

_{N}*) =

*a*

_{N}*.

Using this notation, our summary is:

*a*_{1}* = 1 and*a*_{1}(X) = 1 if and only if X = O, the center of the disk.*a*_{2}* = 1 and*a*_{2}(X_{1}, X_{2}) = 1 if X_{1}= O or X_{2}= O.*a*_{3}* ≤*a*_{3}(O_{1}, O_{2}, O_{3}) = 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 O

_{1}, O

_{2}, and O

_{3}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 5

*x*

^{3}− 4

*x*

^{2}+ 7

*x*− 2, namely

And the resulting greatest area (0.8286369…) can also be expressed exactly as the positive root of the polynomial 160000

*x*

^{6}− 265824

*x*

^{4}+ 412857

*x*

^{2}− 209952, namely

To calculate these values, I first generalized the coordinates of O

_{1}, O

_{2}, and O

_{3}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 5

*r*

^{3}− 4

*r*

^{2}+ 7

*r*− 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:

Dammit Jason, I'm supposed to be working!

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

L. M. A. O.

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.

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.

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.

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

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

Post a Comment