X hits on this document

Powerpoint document

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

67 views

0 shares

0 downloads

0 comments

25 / 26

Establish O(n log2 n) upper bound for LR

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

Establish (n log n) lower bound for LR

Summary

Document info
Document views67
Page views68
Page last viewedThu Dec 08 08:51:42 UTC 2016
Pages26
Paragraphs355
Words1367

Comments