Group:Student Seminar
Title:Finding the Maximum Area Parallelogram in a Convex Polygon
Speaker: Kai Jin University
Time: 2010-12-16 16:00-2010-12-16 17:00
Venue:FIT 1-222


1.We consider the problem of finding the maximum area parallelogram (MAP) inside a convex polygon. We give an algorithm for computing the MAP in an n-sided polygon in time O(n^2), a considerable improvement over the straightforward algorithm which runs in time O(n^4).We achieve our results by proving new structural properties of the MAP, and combining them with a rotating technique of Toussaint [Tou83].2.We also consider the problem of finding the maximum area centrally-symmetric convex body (MAC) inside a convex polygon. We prove that the area of the MAP is always at least 2/π≈ 0.6366 times the area of the MAC. Thus, our algorithm for finding the MAP yields a 2/π-approximation algorithm for this problem.