Saturday, August 6, 2016

An Optimization Problem

Place a point in the interior of a unit disk so that the largest triangle not containing that point has least possible area. 
To describe the problem another way, suppose you and a friend are playing a game. You begin by drawing a dot somewhere inside the disk. Your friend then tries to draw the largest possible triangle (in terms of area) that doesn't contain the dot you drew. No point of your friend's triangle may lie outside the disk, but it's fine if one or more vertices of the triangle touch the boundary of the disk. It's also OK if the boundary of the triangle touches the dot—the dot just can't lie within the triangle's interior. Your objective is to place your dot in such a way that your friend's best triangle will be as small as possible.

Looked at from a distance, the goal here is to minimize a maximum quantity. Problems like that are common in many fields, including game theory (where the goal is to give your opponent only bad options from which to choose), investments, engineering, and quantum mechanics (in my research, I once used a min-max technique to shed a little light on the Heisenberg uncertainty principle).

Getting back to the problem at hand, I think I have the answer, but I haven't made sure of it.

You might also try some generalizations—these I haven't even begun to think about:

  • Place 2 points in the interior of a unit disk so that the largest triangle not containing either of the points has least possible area.
  • Place 3 points in the interior of a unit disk so that the largest triangle not containing any of the points has least possible area.
  • Place N points in the interior of a unit disk so that the largest triangle not containing any of the points has least possible area.
  • Place N points in the interior of a [choose shape] so that the largest [choose shape] not containing any of the points has least possible [length, area, volume].
  • Place N points randomly in the interior of a unit disk. What is the expected value of the area of the largest triangle not containing any of the points?

Feel free to share your results and partial progress on any of the problems. If the problems are standard among researchers (as they may well be), feel free to post some citations as well.

Enjoy!

No comments: