Let P and Q be two disjoint convex polygons in the plane with m and n vertices, respectively. Given a point x in P, the aperture angle of x with respect to Q is defined as the angle of the cone that: (1) contains Q, (2) has apex at x and (3) has its two rays emanating from x tangent to Q. We present algorithms with complexities O(n log in), O(n + n log (m/n)) and O(n + m) for computing the maximum aperture angle with respect to Q when x is allowed to vary in P. To compute the minimum aperture angle we modify the latter algorithm obtaining an O(n + m) algorithm. Finally, we establish an Ω(n + n log(m/n)) time lower bound for the maximization problem and an Ω(m + n) bound for the minimization problem thereby proving the optimality of our algorithms.

Algorithms, Aperture angle, Complexity, Computational geometry, Convexity, Discrete optimization, Robotics, Unimodality, Visibility
School of Computer Science

Bose, P, Hurtado-Diaz, F. (F.), Omaña-Pulido, E. (E.), Snoeyink, J. (J.), & Toussaint, G.T. (G. T.). (2002). Some aperture-angle optimization problems. Algorithmica, 33(4), 411–435. doi:10.1007/s00453-001-0112-9