Some aperture-angle optimization problems

P. Bose, F. Hurtado-Diaz, E. Omaña-Pulido, J. Snoeyink, G. T. Toussaint

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)411-435
Number of pages25
JournalAlgorithmica (New York)
Volume33
Issue number4
DOIs
StatePublished - 2002

Keywords

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

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Some aperture-angle optimization problems'. Together they form a unique fingerprint.

Cite this