X hits on this document

Powerpoint document

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

64 views

0 shares

0 downloads

0 comments

24 / 26

Establishing a Lower Bound of  (n log n)

EVEN-DISTRIBUTION: given n real numbers { x1, x2, ... xn }

check if there exist adjacent xi, xj in the sorted list s.t.  xj - xi > 1

LR must take as least as much time as EVEN-DISTRIBUTION.

But, EVEN-DISTRIBUTION is already known to be in (n log n).

LR algorithm must take (n log n) time

for polygons with degenerate holes.

[McKenna et al. (85)]

O(n) time transformation

orthogonal polygon with degenerate holes

x2

x4

x3

x1

LR area is a solution to the EVEN-DISTRIBUTION instance

Extend to non-degenerate holes using symbolic perturbation.

Document info
Document views64
Page views65
Page last viewedThu Dec 08 06:11:02 UTC 2016
Pages26
Paragraphs355
Words1367

Comments