X hits on this document

Powerpoint document

Finding the Largest Area Axis-Parallel Rectangle in a Polygon in O(n log2 n) Time - page 15 / 26

57 views

0 shares

0 downloads

0 comments

15 / 26

Establish O(n5) upper bound

Characterize the Largest Rectangle (LR)

examine cases based on polygon/LR contacts

Reduce the O(n5) bound to O(n log2 n)

Develop a general framework for dominant case

based on rectangular visibility and matrix total monotonicity

Use divide-and-conquer: T(n) < 2T( | n/2 |) + O(nlogn)

Apply the framework to obtain O(nlogn) for each level

Approach

Document info
Document views57
Page views58
Page last viewedSun Dec 04 08:52:50 UTC 2016
Pages26
Paragraphs355
Words1367

Comments