ALLPOLY - Editorial

general
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Kevin Charles Atienza
Tester: Mugurel Ionut Andreica
Editorialist: Mugurel Ionut Andreica

DIFFICULTY:

HARD

PREREQUISITES:

Kernel of a polygon

PROBLEM:

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.

EXPLANATION:

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

2

I formulated the problem as an intersection of halfplanes - or polygons with \le 5 vertices. My solution afterwards:

  1. look for polygon intersection problems in CF problemset, then solutions to them
  2. find a code which finds a polygon intersection as an intersection of halfplanes
  3. ???
  4. profit!

I really donā€™t like problems which are only hard because they reduce to ā€œimplement this textbook geometry algorithm without missing a tricky corner caseā€.

2 Likes
3

@xellos0 Doesnā€™t it feel like cheating (and boring) to copy algorithms from textbooks? I think everybody should write their own algorithms from scratch.

4

I used the simple method described in the editorial above as ā€˜too slow for the given limitsā€™. It was fast enough to get 100 p.

5

i had a different idea to solve , though i couldnt code it but it is quite general i guess . so all the edges can be seen as a set of inequalities and we have to find its common area . now how to find common area ? . lets divide the lines into two sets , a lower hull and an upper hull .

for example , let there be a triangle ABC with base BC , now we are sure that sides AB and BC will give us an upper boundations . so AB , BC goes to upper hull and BC goes to lower hull , now see there are many lines, we can do this for every line in just one pass in clockwise direction . so cool .

Now , we have two sets , lets apply CHT trick over this , remember i am not saying graham scan or something , yes that thing which we use in dp optimisations , which gives us a set of line segments which are max/min of every x . cool , so just minimise the upper hull and maximise the lower hull for every x. we can do this in nlogn after sorting on basis of the slope , we dont need the dynamic variant . now we can merge these two hulls , this will give us a polygon . the area of this polygon is what we need . I will explain the test case , here U denotes that this line will go to upper hull and U denotes that this will go to lower hull

![alt text][1]
[1]: https://discuss.codechef.com/upfiles/Screen_Shot_2016-07-20_at_7.49.44_PM.png

6

Itā€™s boring to write a textbook algorithm, and using a freely available resource is not cheating.

If thereā€™s a problem that requires implementing [insert something hard to implement and very long yet well-known to be available online], would you spend days just trying to write it correctly?

Algorithmic programming is about efficiency. To me, that means efficiency of programmers as well as programs.

1 Like