Thursday, September 15, 2016

Points In A Circle Problem: Update on N = 3

For the configuration of obstacle points shown below, nobody has yet found a valid triangle with area greater than about 0.829. Recall that a triangle is valid as long as it doesn't strictly contain any of the obstacle points.

The obstacle points shown above are equally spaced around a circle of radius 0.32096.... Given these obstacle points, the greatest area I can find for a valid triangle is 0.82863..., attained by the two triangles shown below.

(Reader Matt found these as well.) 

I call the first triangle "the edge triangle," and I call the second triangle "the spotlight triangle."

The reason I placed the obstacle points a distance 0.32096... from the center is that doing so gives the edge triangle and the spotlight triangle equal areas. If the obstacle points were to move closer to the center, the area of the edge triangle would increase and the area of the spotlight triangle would decrease; if the obstacle points were to move further from the center, the area of the spotlight triangle would increase and the area of the edge triangle would decrease. The greater of the two areas is minimized when the obstacle points are as shown. It is on the strength of that circumstance that I guessed these obstacles as minimizing the maximum area over valid triangles.

Anyhow, recently I had a bit of downtime, so I wrote a quick program to look randomly for valid triangles with area greater than 0.82863.... To do that, I first generated 1,000 points distributed randomly over the disk:

These thousand points determine 166,167,000 triangles. I went through those triangles, discarding any of them with area less than 0.815. What remained was a list of about 1.6 million large triangles. I checked this list to see if any of the large triangles were valid. However, none of them were. 

So, this particular attempt at beating the record 0.82863... failed. 

Here are some of the large triangles that were closest to being valid:

It looks as if these triangles are "trying" to be like the spotlight triangle, with one case of an edge triangle. (I think edge triangles are less well represented because they have fewer ways to avoid the obstacles without losing area rapidly by sacrificing altitude.)

Anyway, this exercise increases my confidence somewhat that the edge triangle and the spotlight triangle are indeed maximizers for the obstacle points shown, and that up to symmetry these two triangles are the only maximizers.

Of course, none of this is a proof of anything.

Some notes on the program: 

  • Calculating area is much faster than checking validity. That's why I calculated 166,167,000 triangle areas first, and then checked only the largest triangles for validity. It would have been impractically slow to work in the reverse order (checking 166,167,000 triangles for validity and then calculating the areas for the subset found to be valid). Calculating 166,167,000 triangle areas took about 12 hours. (If I do this again, I'll see if I can optimize the area calculation.)  
  • In the validity test, I'm using barycentric coordinates to determine whether a given point is contained by a given triangle. I'm not sure the barycentric test is faster than one based on same-side-of-line considerations, but so far I haven't needed to worry about speed in this phase of things. (Also, barycentric coordinates make it easy to be quantitative in various ways, for example identifying triangles that are close to valid, as shown in the animation above.)
  • 166,167,000 triangles is a lot of triangles, so the program never holds all of them in memory. Instead of generating all those triangles ahead of time, I put the area test inside a threefold-nested loop over the thousand randomly selected points. Triples of points passing the area test were added to a steadily growing list of large triangles. 


Lisa B said...

I'm curious what your reasoning is behind common core. My children are in 2nd Grade and 4th Grade. I don't understand why it takes 3 subtraction problems to solve 1. It's insane and absolutely ridiculous. We do not need to dumb down the math process for kids. 15-7=8 I should not have to make a 10 to make it easier. It's the most ridiculous method I've ever seen. Maybe In High school your process makes it's easier for teens to learn but it's ridiculous for young children.

Jason Zimba said...

For the curious, the following articles by me will be of interest:

The Development and Design of the Common Core State Standards for Mathematics. New England Journal of Public Policy, Vol. 26, Issue 1 (2014).

A New Course for K–12 Mathematics Education. Guest post for Johns Hopkins University Press.

Can parents help with math homework? YES

Common Core standards emphasize ‘math that matters most.’ Interview.

The Developmental Appropriateness of the Common Core State Standards for Mathematics

The Common Core and the Potential for Mathematicians to Improve the Teaching of School Mathematics. Notices of the American Mathematical Society, Volume 63, Number 2, pp. 154–158.

See also: See also previous Saturday School posts,