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

83 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 views83
Page views84
Page last viewedTue Jan 17 09:01:29 UTC 2017
Pages26
Paragraphs355
Words1367

Comments