Finding the largest area axis-parallel square with a known center in a polygon

Finding the maximum volume shape that will fit inside of another shape is a common class of geometric optimization problem that occurs in many applications (computer graphics, collision detection, GIS, etc.). General problem formulations, such as finding the largest area axis-parallel rectangle in a polygon, involve complex analysis and do not have simple algorithmic solutions that are easy to implement.

Finding the largest area axis-parallel square with a known center in a polygon is a sufficiently restricted problem to admit a simple O(n) time and O(1) space solution. The analysis, algorithm, and implementation are very straightforward. I have found this problem formulation useful in computing cropping regions for eye images stenciled by hidden area meshes in virtual reality systems, but it should be general enough to be useful in other contexts.

Continue reading