NobleBlocks

Research indexThesis

Aperture angle optimization problems

Omaña-Pulido

eScholarship@McGill (McGill)1 Jan 1994Open access

NobleIDark:/48914/w1/20261105/F0C94C82DOI10.82308/1532

Abstract

Let Q be a convex polygon in $E sp2$ and x be a point in $E sp2$ not contained in Q. The aperture angle $ theta(x)$ with respect to Q is defined as the angle subtended by the cone that: (1) contains Q, (2) has apex at x, and (3) has its two rays emanating from x tangent to Q. The Aperture-Angle Problem in the Euclidean Plane $E sp2$ is defined as follows: Given two disjoint convex sets P and Q in $E sp2$, find a point $X in P$ such that $ theta(X)$ is the maximum value of the aperture angle function, and a point Z in P such that $ theta(Z)$ is the minimum value. We present an $O(n+m)$ time algorithm for computing the minimum aperture angle with respect to a convex polygon Q when x is allowed to vary in a convex polygon P(n and m are the number of vertices, respectively). We also present algorithms with complexities $O(n log m)$ and $O(n+m)$ for computing the maximum aperture angle with respect to Q. To compute the minimum aperture angle we modify the latter algorithm obtaining an $O(n+m)$ algorithm. Finally, we prove an $ Omega(n)$ time lower bound for the maximization and minimization problems, and an $ Omega(m)$ time lower bound for the minimization problem. In three dimensions we find the solution to the following problem: Given a convex polyhedron K and given a segment ab that does not intersect K, find a point X $ in$ K such that the aperture angle defined as ang(aXb) is the maximum of the aperture angle function. We present a solution whose time complexity is linear with respect to the number of edges of K, i.e., it is O(n) if the corresponding convex polyhedron K has n vertices. We prove an $ Omega(n)$ time lower bound for this problem.

Discussion

More

Suggest a correction or report