Scan line algorithm for intersecting polygonsGiven two sets of polygons P 1 = { s 1 , . . . , s m } and P 2 = { s m + 1 , . . . , s n } with total number of n segments, the previous and next segment on it's polygon can be determined in O(1). Describe a scan-line algorithm that computes all points of P 1 ∩ P 2 in O(n).

Question

Scan line algorithm for intersecting polygonsGiven two sets of polygons       P    1    =  {      s    1    ,  .  .  .  ,      s    m    } and       P    2    =  {      s    m    +  1  ,  .  .  .  ,      s    n    } with total number of n segments, the previous and next segment on it&#039;s polygon can be determined in O(1). Describe a scan-line algorithm that computes all points of       P    1    ∩      P    2   in O(n).

Bridget Vang · Accepted Answer

Explanation:This is not possible, as the number of intersections can be   O  (      n    2    )

Given two sets of polygons P_1={s_1,...,s_m} and P_2={s_m+1,...,s_n} with total number of n segments, the previous and next segment on it's polygon can be determined in O(1). Describe a scan-line algorithm that computes all points of P_1 cap P_2 in O(n).

Answered question

Answer & Explanation

New Questions in High school geometry