X hits on this document

Powerpoint document

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

65 views

0 shares

0 downloads

0 comments

5 / 26

Given a 2D polygon that:

does not intersect itself

may have holes

has n vertices

Find the Largest-Area Axis-Parallel Rectangle

How “hard” is it?

How “fast” can we find it?

What’s the Problem?

n

1

n log(n)

n log2(n)

2n

n5

n (n) log(n)

n (n)

Document info
Document views65
Page views66
Page last viewedThu Dec 08 08:13:07 UTC 2016
Pages26
Paragraphs355
Words1367

Comments