The Art Gallery Guardian

Given sequence of angles, find a polygon


Problem1

Find a polygon , such that the angle at vertex is .

Define for a polygon . If one consider a polygon’s sides are vectors, then a polygon is set of vectors that equals to 1, such that the magnitude of the vectors are greater than 0.

Angles at each vertex determines the direction of the vector. Let be the unit vector with direction of , we have

for all . can be computed from trivially. We assume we have normalized the polygon by rotate it, so . Once we find a set of , then we determine a solution to the problem. is in the intersection of the solutions of two set of linear systems. One might first calculate the solution to the linear systems individually, then take the intersection, and pick a point where all coordinates are positive.

This is not easy to code, and it take time to just solve the linear system. A better and faster solution exploits the fact we are operating in a small dimension.

Observe that a polygon lies on a plane, a 2D space, we might think we can arbitrarily put down the length of vectors, and calculate the last one from it. It is not true, the condition shows does not contain the origin unless .

If we can find , such that the convex hull of them contains the origin (here the convex hull means the open polygon contained inside), then clearly we can use to span the entire plane. The span here is defined as all the values can be obtained from conical combination. This inspires the following algorithm:

Find that spans the entire plane by checking if the convex hull contains . Arbitrarily assign , such that . Calculate and from the assignment.

Once are found, only time is required to find the polygon. Find the three spanning vectors is linear time. Pick any two adjacent vectors as , and do a search for that satisfy the condition. One can find a solution in time.

If the algorithm fails, there are two possibilities:

  1. There is no such polygon.
  2. There are only four directions, and they are exactly . We can solve this special case by arbitrarily assign except the 2 of the directions. Calculate the length for those two from the other ones. This special case can be solved in time too.
Posted by Chao Xu on .
Tags: computational geometry.