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

97 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 views97
Page views98
Page last viewedSun Jan 22 11:04:17 UTC 2017
Pages26
Paragraphs355
Words1367

Comments