TY - JOUR

T1 - Aperture-Angle Optimization Problems in Three Dimensions

AU - Omaña-Pulido, Elsa

AU - Toussaint, Godfried T.

N1 - Funding Information:
Research supported by NSERC Grant No. OGP0009293 and FCAR Grant No. 93-ER-0291.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - algorithms

KW - aperture-angle

KW - computational-complexity

KW - convexity

KW - discrete-optimization

KW - geometry

UR - http://www.scopus.com/inward/record.url?scp=73349108020&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=73349108020&partnerID=8YFLogxK

U2 - 10.1023/A:1021666512528

DO - 10.1023/A:1021666512528

M3 - Article

AN - SCOPUS:73349108020

SN - 1570-1166

VL - 1

SP - 301

EP - 329

JO - Journal of Mathematical Modelling and Algorithms

JF - Journal of Mathematical Modelling and Algorithms

IS - 4

ER -