Sunday, October 16, 2016

Points In A Circle Problem: Solution For N = 1

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.

My conjectured solution for N = 3 is shown below. The three obstacle points are equally spaced around a circle, the radius of which is chosen so that the two triangles shown below have the same area.




How about the N = 1 version of the problem?
Place a point in the unit disk in such a way as to minimize the greatest possible area of a triangle in the unit disk that doesn't contain the point.
It is intuitively compelling that the best location for the obstacle is the center of the disk, and this in fact is the case. Putting the obstacle point at the center limits the greatest possible triangle area to 1, as shown below.



For any other location of the obstacle point, there exists a triangle of area greater than 1 that doesn't contain the point. Here's what that situation looks like in a particular case.



I won't post a detailed version of my solution to the N = 1 case, because my approach was pretty weedy—in part because I was retrofitting ideas that I'd generated while thinking about the N = 3 case. Maybe there's a fast way to get straight to the answer for N = 1?

At any rate, here was my approach in outline:

1. Establish some facts that reduce the number of possibilities.

     (i) For any placement of the obstacle point, a greatest-area triangle not containing the obstacle point must have all three vertices on the boundary of the disk.

The approach here is to show that if a triangle has a vertex in the interior of the disk, then the area of the triangle can be increased, without losing feasibility, by nudging vertices a sufficiently small distance. This looks a little different depending on whether the obstacle point is initially outside the triangle, or at a vertex of the triangle, or on a side of the triangle.

(In the first of these cases, you have to show that a point initially outside a triangle remains outside when a vertex is nudged a sufficiently small distance. This probably isn't hard to show using elementary methods, but it's a snap if you happen to know about barycentric coordinates.)

     (ii) Given two vertices in a greatest-area triangle not containing the obstacle point, the remaining vertex must be one of a finite number of possibilities. 

The feasible region for the third vertex turns out to be an arc on the boundary of the disk. Sliding the third vertex along this arc by a small amount increases the area of the triangle—unless the third vertex is one of the endpoints of the arc, or else one of the two places on the boundary of the disk where sliding the third vertex doesn't gain you any area (because sliding moves you parallel to the base of the triangle).

     (iii) If a greatest-area triangle not containing the obstacle point doesn't have the obstacle point on its boundary, then the triangle is an inscribed equilateral triangle.

This is basically a special case of (ii), in which the only possibilities for the third vertex are the two special places where sliding the third vertex doesn't gain you any area. The upshot is that the triangle must be isosceles on each of its bases, and therefore equilateral.

2. Use the above facts to determine an explicit function a(r) giving the area of a greatest-area triangle not containing an obstacle point located a distance r from the center of the disk.

Here is a sketch of the case \(0 < r < \frac{1}{2}\). Let the obstacle point be given, and consider a greatest-area triangle that doesn't contain the obstacle point. By (i), all three triangle vertices lie on the boundary of the disk. By (iii), some edge of the triangle touches the obstacle (because an equilateral triangle isn't feasible for \(r < \frac{1}{2}\); the incircle of an equilateral triangle has radius \(\frac{1}{2}\), so no matter how the triangle is rotated, it will contain an obstacle with \(r<\frac{1}{2}\)). Denoting the angle of that edge (as measured from the horizontal) by θ, a little trigonometry gives the length of the side as \(2\sqrt{1-r^2\sin^2\theta}\). The altitude is found with the help of (ii) as \(1 + r\sin\theta\). So the triangle area is \((1+r\sin\theta)\sqrt{1-r^2\sin^2\theta}\). Differentiating with respect to θ, we find that the area attains a maximum value \((1+r)\sqrt{1-r^2}\) when \(\theta = \frac{\pi}{2}\).

The result of analyzing the full range of possible r values is \(a(r) = (1 + r)\sqrt{1 - r^2}\) for \(0 \leq r \leq \frac{1}{2}\) and \(a(r) = \frac{3\sqrt{3}}{4}\) for \(\frac{1}{2} \leq r \leq 1\).

3. Show that the unique minimum of a(r) occurs when r = 0. Thus, the unique best location of the obstacle point is the center of the disk.

Straightforward, in view of the fact that we have the explicit function a(r).

So much for N = 1. Maybe I'll start devoting my subway rides to the N = 2 problem now!

P.S. I doubt that principle 1(i) holds for arbitrarily large N.

No comments: