讨论组:研究生会议
标题:Finding the Maximum Area Parallelogram
演讲人: 金恺 University
时间: 2011-04-07 12:00-2011-04-07 13:00
地点:FIT 1-222

内容:

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 introduced by Toussaint [Tou83].

 

Last time in theory lunch I've gave a proof that the area of the MAP is always at least 2/π times the area of the maximum area centrally-symmetric convex body(MACC) inside it. Thus, our algorithm for finding the MAP yields a 2/π-approximation algorithm for finding the MACC inside a convex polygon; This time I'll mainly talk about the techniques using in our algorithm that improve the running time from O(n^4) to O~(n^2).  And I'll give the bottleneck of my algorithm, where requires O((nlogn)^2) time and other parts only require O(n^2) time.



人物介绍: