X hits on this document

Powerpoint document

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

70 views

0 shares

0 downloads

0 comments

23 / 26

Establishing a Lower Bound of  (n log n)

MAX-GAP instance: given n real numbers { x1, x2, ... xn } find the maximum difference between 2 consecutive numbers in the sorted list.

O(n) time transformation

self-intersecting,

orthogonal polygon

x2

x4

x3

x1

LR area is a solution to the MAX-GAP instance

LR algorithm must take as least as much time as MAX-GAP.

But, MAX-GAP is already known to be in (n log n).

LR algorithm must take (n log n) time

for self-intersecting polygons.

Document info
Document views70
Page views71
Page last viewedFri Dec 09 22:50:35 UTC 2016
Pages26
Paragraphs355
Words1367

Comments