[Math] Scan line algorithm for intersecting polygons

Question

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).$

Answer 1

The algorithm used for this can be the Bentley-Ottman algorithm, Which uses a sweep line. Visit this link for more info (http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm)