X hits on this document

Powerpoint document

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

55 views

0 shares

0 downloads

0 comments

14 / 26

O(n5) LR Algorithm

Find_LR(Polygon P)

  area0        Find_LR_0_RC(P)

  area1        Find_LR_1_RC(P)

  area2        Find_LR_2_RC(P)

  area3        Find_LR_3_RC(P)

  area4        Find_LR_4_RC(P)

  return maximum(area0, area1, area2, area3, area4)

Find_LR_0_RC(P)

for i       1  to n  [for each edge of P]

       for j       1  to n

     for k       1  to n

        for l       1  to n

            area        area of LR for 0-RC determining set for (i,j,k,l)

     if LR is empty, then update maximum area

     return maximum area

O(n)

O(n5)

Document info
Document views55
Page views56
Page last viewedFri Dec 02 20:36:54 UTC 2016
Pages26
Paragraphs355
Words1367

Comments