Given a (not necessarily convex) polygon, find the area of its kernel. The kernel of a polygon is the set of points in the plane from which every point inside the polygon (including on its edges) is visible. The kernel can be empty.
We can stop thinking about the given polygon as a polygon, and see it as a collection of half-planes. Each edge of the polygon defines a half-plane (oriented towards the inside of the polygon). The problem can be re-stated as computing the area of the intersection of N half-planes with the square $[-10^7,10^7]x[-10^7,10^7]$.
A simple solution is to consider the half-planes in any order and “clip” the current kernel. We start with the kernel being the full square. Then, for every half-plane, we verify if it intersects any edge of the kernel. There are 3 possibilities:
- the full kernel is inside the half-plane: in this case there’s nothing to be done and we continue to the next half-plane
- the full kernel is outside the half-plane: in this case the kernel becomes empty and we stop
- the half-plane intersects the kernel in two points: we find these intersection points and “clip” the kernel
Each half-plane may add one extra vertex to the kernel. Thus, the kernel may end up having O(N) vertices. Then, if we test every half-plane for intersection against every edge of the kernel, this test may take O(N) per half-plane. Thus, the overall time complexity of this approach is O(N^2), which is too slow for the given limits.
Let’s now optimize this approach. We will sort all the N half-planes according to their slope and we will consider them in this order. For the first half-plane we proceed as before. After every half-plane we can have one of the 3 outcomes mentioned above. If the kernel becomes empty we can stop. Otherwise, we will also remember a vertex q. If the half-plane intersected the kernel, q will be one of the two intersection points. If the half-plane did not intersect the kernel, then q will be the kernel’s vertex which is closest to the line defining the half-plane.
When we move to the next half-plane we move along the kernel’s boundary from vertex to vertex, starting from the vertex q obtained at the previous half-plane. When moving along the kernel’s boundary we stop either when we find a vertex outside of the half-plane or when we reach the vertex which is closest to the half-plane’s line. Deciding if a vertex p is the closest to the half-plane’s line is simple: p must be closer than (or at the same distance as) both of its two neighbors along the kernel boundary.
If we found a vertex outside the half-plane then we move along the kernel’s boundary along both directions starting from that vertex, either until we find the two intersection points or until we discover that all the vertices of the kernel are outside the half-plane.
Although this approach can take O(N) time for some half-planes, an asymptotic analysis will show that it takes only O(N) time overall. The overall time complexity is O(NlogN), from the need to sort the half-planes initially according to their slopes.
This problem can also be solved through several other approaches, so please discuss in the answers/comments which approaches you used.
AUTHOR’s AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here. It implements the approach presented in the editorial (actually, both the fast and the slow approaches can be found in the source code).