The Art Gallery Guardian

Given sequence of angles, find a polygon


Problem1

Find a polygon p1pnp_1\ldots p_n, such that the angle at vertex pip_i is αi\alpha_i.

Define pn+1=p1p_{n+1} = p_1 for a polygon p1pnp_1\ldots p_n. 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 uiu_i be the unit vector with direction of pipi+1p_ip_{i+1}, we have

i=1nciui=0 \sum_{i=1}^n c_iu_i = 0

ci>0c_i>0 for all ii. uiu_i can be computed from αi\alpha_i trivially. We assume we have normalized the polygon by rotate it, so u1=(0,1)u_1=(0,1). Once we find a set of cic_i, then we determine a solution to the problem. (c1,,cn)(c_1,\ldots,c_n) 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 O(n3)O(n^3) 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 n1n-1 vectors, and calculate the last one from it. It is not true, the ci>0c_i>0 condition shows {c1u1+c2u2c1,c2>0}\set{c_1u_1+c_2u_2|c_1,c_2>0} does not contain the origin unless u1=u2u_1=-u_2.

If we can find u1,u2,u3u_1,u_2,u_3, 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 u1,u2,u3u_1,u_2,u_3 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 ux,uy,uzu_x,u_y,u_z that spans the entire plane by checking if the convex hull contains (0,0)(0,0). Arbitrarily assign cic_i, such that iy,zi\neq y,z. Calculate cyc_y and czc_z from the assignment.

Once ux,uy,uzu_x,u_y,u_z are found, only O(n)O(n) time is required to find the polygon. Find the three spanning vectors is linear time. Pick any two adjacent vectors as ux,uyu_x,u_y, and do a search for uzu_z that satisfy the condition. One can find a solution in O(n)O(n) 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 (1,0),(0,1),(1,0),(0,1)(1,0),(0,1),(-1,0),(0,-1). We can solve this special case by arbitrarily assign cic_i except the 2 of the directions. Calculate the length for those two from the other ones. This special case can be solved in O(n)O(n) time too.
Posted by Chao Xu on .
Tags: computational geometry.