X hits on this document

Powerpoint document

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

66 views

0 shares

0 downloads

0 comments

19 / 26

Theorem: The LR in an n-vertex general polygon can be found in O(n log2 n) time.

Partitioning the polygon with a vertical line produces a vertically separated, horizontally convex polygon for the merge step of divide-and-conquer.

LR Algorithm for a General Polygon

Document info
Document views66
Page views67
Page last viewedThu Dec 08 08:23:54 UTC 2016
Pages26
Paragraphs355
Words1367

Comments