X hits on this document

Powerpoint document

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

60 views

0 shares

0 downloads

0 comments

18 / 26

Monotonicity and Aggarwal et al.’s matrix searching-based O(nlogn) algorithm for the LECR problem lead to the following:

Lemma: The LR in an n-vertex vertically separated, horizontally convex polygon can be found in      O(n log n) time.

Goal: Produce a vertically separated, horizontally convex polygon for the merge step of divide-and-conquer.

LR Algorithm for a General Polygon

Lemma: If V’ and E’ are y-monotone, then M defined by our LR-measure (“area”) is totally monotone.

Document info
Document views60
Page views61
Page last viewedMon Dec 05 23:39:35 UTC 2016
Pages26
Paragraphs355
Words1367

Comments