PROBLEM LINK:Author: tuananh93 DIFFICULTY:HARD PREREQUISITES:Computational geometry, Point location, Scan line, Selfbalancing binary search tree, Functional programming PROBLEM:Given N simple polygons, among which there don't exist two polygons that share a common point. QUICK EXPLANATION:Let's consider a query point P(a,b). EXPLANATION:My main idea follows the quick explanation above. Let's consider a query point P(a,b). In order to check if P is a vertex of a polygon or if P is on an edge of a polygon which is perpendicular to the Xaxis, we need a set VertexSet to store all the vertices and a set EdgeSet to store all the edges of the polygons which is perpendicular to the Xaxis. Notice that an edge perpendicular to the Xaxis can be regarded as a triple (x,l,r) (l<=r) which means the endpoints of the edge is (x,l) and (x,r). To check a point P, we can check if P is in set VertexSet or if there exists an edge (x,l,r) in set EdgeSet which satisfies x==a and l<=b<=r. We can use a selfbalancing binary search tree to make set VertexSet and use a selfbalancing binary search tree to make set EdgeSet. After check the boundary conditions, we can ignore all the edges that are perpendicular to the Xaxis. Now we'll go to the topic. An edge can be regarded as a tuple (x1,y1,x2,y2) (x1 < x2) which means the endpoints of the edge is (x1,y1) and (x2,y2), and we call (x1,y1) the left endpoint and call (x2,y2) the right endpoint. Let's consider the line L:x=a, find out the set S, which consists of all the edges of the polygons which intersect with line L. Thus we can determine if P is in or on a polygon by set S. Let's say line A is considered to be greater than line B if line A is above line B. Notice that in this problem all the edges may only intersect on the endpoints, which means all edges in set S can be sorted. Then we can make a scan line for each x through the Xaxis. Initially, set S sets empty. We notice that set S changes at some x only when there exists an endpoint of a polygon. Thus we find out all the endpoints and make them sorted as an array {x[0],x[1],...,x[t1]}. Now for each x[i] (0<=i< t), we delete all the edges whose right endpoint (x2,y2) satisfies x2==x[i] and then insert all the edges whose left endpoint (x1,y1) satisfies x1==x[i]. Set S currently is the scan line of any x (x[i]<=x<=x[i+1]). For convenience, S(a) is denoted the set S when x=a. Use functional programming to store the history version of set S at any time. Now come back to the query point P(a,b). We should find a history version of set S which corresponds to S(a). We can determine if P is in or on a polygon by set S(a). Firstly, find the least edge U in set S(a) which P is below or on and the greatest edge D in set S(a) which P is above or on. if P is on U or P is on D, the polygon containing the point P has been found. Count the number of edges which is less than or equal to D, if it is even, then P is not contained by any polygon, if it is odd, then P is contained by the polygon whose edge D is. So while we are dealing with set S as a binary search tree, maintenance the information that the number of nodes of the subtree of each node of S in order to count the number of edges which is less than or equal to some line. In this way, we can solve the problem in both time and space complexity O(nlogn). ALTERNATIVE SOLUTION:There may be other ways to solve the problem, for example, Trapezoidal decomposition, a more general solution to Point location. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here(admin, please add).
This question is marked "community wiki".
asked 16 Dec '13, 10:05

The approach is amazing but it might be nice to explain in detail the 'functional programming' part (computing all history versions), because probably not many people are familiar with that.