Shepherd's Problem

Post date: Jan 9, 2013 2:24:26 AM

The problem I will discuss today is Problem I of the 26th Andrew Stankevich Contest (available as a codeforces gym), named Shepherd's Problem. The problem is: given

points

on a plane, and two values and , find a point on the plane such that:

This could have some interesting applications in computer graphics, such as if you are given a bunch of interesting objects and the limits of your view frustrum, find the best location to place the camera; or perhaps it could be used to optimize placements of security cameras to minimize the blind spots by reducing their turning radius. But who cares about the applications, let's solve this problem.

One immediate observation is that if there is a solution, it must lie exactly at a distance from at least one of the input points, because if it doesn't, then it can be moved "further away" and make the angle smaller. Together with the distance constraints and that it cannot be in the convex hull of the points, we can conclude that the optimal point must be somewhere on the yellow line that is not inside a red circle or the blue triangle.

The question now is, how do you represent and code this, and how do you search for the optimal point on those lines? Let's simplify the question a bit so we only consider one green circle, instead of that weird intersected segment. Thus, we want to find the location on a given green circle that's valid and minimizes the viewing area. If we can solve this for every green circle, we can just take the valid solution that has the minimal viewing area out of all of the solutions. For the rest of this post I will work with the bottom green circle, but remember that the process needs to be repeated for every one of them.

which splits the circle into two segments, and , one of which is valid and one of which is not. Similarly, we can intersect the circle with the convex hull of the input points. If we gather all of these intersections together and sort them, we get a set of numbers

, with the property that the segment is either entirely valid, or entirely invalid. To test whether it is valid, we just pick some point, say the midpoint, and check all of the constraints. The following picture is an example of separating into these segments.

Now, for each valid segment we just need to find the point that minimizes the viewing area. Unfortunately, there are no guarantees on the form of the function for the viewing area, at least, not on these segments. What is needed is the observation that if you are calculating the viewing area for two fixed points, then the function is quadratic.

But, when could we possibly change which two points we use to calculate the viewing angle? Why, only when a point becomes visible/invisible of course! And those points are merely the intersection of all the lines through each pair of points with the circle. So, just add those intersection points to our set too, and we now have a set of segments such that

• Each segment is either entirely valid or entirely invalid
• The function for viewing angle is quadratic on each segment.

The algorithm is now simple. For each segment, check if it is valid, and if it is, run ternary search on it to find the location with the minimum viewing angle. Take the location with minimum viewing angle out of all of the segments, out of all of the circles you start with, and that is the answer. If there is no valid location, then output impossible.

My implementation can be found here. Two functions used that might be good to know about include arg and polar (WARNING: do not use those if your point is complex<int>!!!).

Cheers!