QPOINT - Editorial

PROBLEM LINK:

Practice
Contest

Author: tuananh93
Editorialist: liouzhou_101

DIFFICULTY:

HARD

PREREQUISITES:

Computational geometry,
Point location,
Scan line,
Self-balancing binary search tree,
Functional programming

PROBLEM:

Given N simple polygons, among which there don’t exist two polygons that share a common point.
You are forced to answer Q queries online. Each query requires you to find a polygon that contain a specific point, or make a conclusion that no polygon contains the specific point. Note that a point on an edge of an polygon is considered to be contained by the polygon.

QUICK EXPLANATION:

Let’s consider a query point P(a,b).
Check if P is a vertex of a polygon or if P is on an edge of a polygon which is perpendicular to the X-axis.
If either, you’ve found the very polygon.
If neither, 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.
In order to deal with the online queries, we should use a functional self-balancing binary search tree to store the history version of each scan line.
Thus, we can solve the problem in both time and space complexity O(nlogn).

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 X-axis, 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 X-axis. Notice that an edge perpendicular to the X-axis 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 self-balancing binary search tree to make set VertexSet and use a self-balancing binary search tree to make set EdgeSet.

After check the boundary conditions, we can ignore all the edges that are perpendicular to the X-axis. 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 X-axis. 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[t-1]}. 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).
Tester’s solution can be found here(admin, please add).
Editorialist’s solution can be found here.

3 Likes

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.