## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 411-435 |

Number of pages | 25 |

Journal | Algorithmica (New York) |

Volume | 33 |

Issue number | 4 |

DOIs | |

State | Published - 2002 |

## Keywords

- Algorithms
- Aperture angle
- Complexity
- Computational geometry
- Convexity
- Discrete optimization
- Robotics
- Unimodality
- Visibility

## ASJC Scopus subject areas

- Computer Science(all)
- Computer Science Applications
- Applied Mathematics