2002-01-01

# Some aperture-angle optimization problems

## Publication

### Publication

*Algorithmica , Volume 33 - Issue 4 p. 411- 435*

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.

Additional Metadata | |
---|---|

Keywords | Algorithms, Aperture angle, Complexity, Computational geometry, Convexity, Discrete optimization, Robotics, Unimodality, Visibility |

Persistent URL | dx.doi.org/10.1007/s00453-001-0112-9 |

Journal | Algorithmica |

Citation |
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 |