TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Monday, September 05, 2022

Least Area Quadrilateral that contains a set of N planar points

Question: How does one find the least area quadrilateral (not necessarily convex) that contains a given set of N points in general position on the plane?

The least area containing quadrilateral (non-convex) could be degenerate in some cases - the union of a triangle and an infinitely thin 'sliver'. By general position, we mean no three points are collinear. And if there are more than 4 points in total, the quad, even if it has a degenerate portion, will not be of zero area.

Can one say that a least area quadrilateral (such a quadrilateral may not be unique) will have at least one edge flush with an edge of the convex hull of the set of n points? Or maybe one can ask, if *every* least area quad containing the points has an edge flush with an edge of the convex hull. I really don't know.

Note: The question has a natural generalization to finding least area m-gons that contain N points on the plane.
-----------
The above question is copied from a Mathoverflow post.

0 Comments:

Post a Comment

<< Home