Aperture-Angle Optimization Problems in Three Dimensions

Elsa Omaña-Pulido, Godfried T. Toussaint

Research output: Contribution to journalArticle

Abstract

Let [a,b] be a line segment with end points a, b and ν a point at which a viewer is located, all in R 3. The aperture angle of [a,b] from point ν, denoted by θ(ν), is the interior angle at ν of the triangle Δ(a,b,ν). Given a convex polyhedron P not intersecting a given segment [a,b] we consider the problem of computing θmax(ν) and θmin(ν), the maximum and minimum values of θ(ν) as ν varies over all points in P. We obtain two characterizations of θmax(ν). Along the way we solve several interesting special cases of the above problems and establish linear upper and lower bounds on their complexity under several models of computation.

Original languageEnglish (US)
Pages (from-to)301-329
Number of pages29
JournalJournal of Mathematical Modelling and Algorithms
Volume1
Issue number4
DOIs
StatePublished - Dec 1 2002

    Fingerprint

Keywords

  • algorithms
  • aperture-angle
  • computational-complexity
  • convexity
  • discrete-optimization
  • geometry

ASJC Scopus subject areas

  • Modeling and Simulation
  • Applied Mathematics

Cite this