X hits on this document

Powerpoint document

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

72 views

0 shares

0 downloads

0 comments

20 / 26

O(n log2 n) LR Algorithm

Find_LR(Polygon P)

  preprocess P

  H, V        horizontal, vertical visibility maps of P

       P        P  U internal vertex projections

   return   LR_DivideConquer(P, H, V)

LR_DivideConquer(P, H, V)

if  P.numVertices is “too small”calculate &  return LR area

    Pleft ,  Pright        left, right parts of P     L    [vertical partitioning line]

Hleft , Hleft , Vleft , Vright            H, V updated for       L

    arealeft            LR_DivideConquer(Pleft , Hleft , Vleft)

    arearight           LR_DivideConquer(Pright, Hright , Vright)

     Q          U1<=i<=k   Qi          [L may contain k partitions]

     areaQ         LR_HV_DivideConquer(Q)  

return maximum(arealeft , arearight, areaQ )

O(n log n)

O(n log2 n)

O(n log n)

T(n) < 2T( | n/2 |) + O(nlogn)

T( | n/2 |)

T( | n/2 |)

Document info
Document views72
Page views73
Page last viewedSat Dec 10 03:23:13 UTC 2016
Pages26
Paragraphs355
Words1367

Comments