X hits on this document

Powerpoint document

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

69 views

0 shares

0 downloads

0 comments

16 / 26

A General Framework for the 2-Contact Case

Definition: M is totally monotone if, for every i<i’ and j<j’ corresponding to a legal 2x2 minor, mij’ > mij implies mi’j’ > mi’j

24

15

27

24

b

c

a

1

2

3

10

14

6

20

15

a

b

c

1

2

3

Theorem [Aggarwal,Suri87]: If any entry of a totally monotone matrix of size mxn can be computed in O(1) time, then the row-maximum problem for this matrix can be solved in (m+n) time.

A General Framework for the 2-Contact Case

Area Matrix M for “empty corner rectangles”

LR is the Largest Empty Corner Rectangle (LECR)

Document info
Document views69
Page views70
Page last viewedFri Dec 09 17:33:21 UTC 2016
Pages26
Paragraphs355
Words1367

Comments