A unified approach to conic visibility
In this paper we present linear time algorithms for computing the shortest path tree from a point and the weak visibility polygon of an are inside a triangulated curved polygon. We also present a linear time algorithm for computing the planar subdivision (in the parametric space) of the set of rays emanating from a fixed are, such that each face of the subdivision corresponds to rays hitting the same are of the polygon. Although these results, which involve nontrivial generalizations of known results for rectilinear polygons, may have some interest in its own right, the main result of this paper is a linear time algorithm for computing the conic (circular, elliptic, parabolic, and hyperbolic) Visibility polygon of a point inside a simple polygon. The main advantage of our technique over previous results on circular visibility is that it provides a simple, unified approach to conic visibility. Finally, we present a linear time algorithm for computing the planar subdivision, in the parametric space, of two-parametric families of conic rays emanating from a fixed point, such that each face of the subdivision corresponds to conic rays hitting the same edge of the polygon. All these algorithms are asymptotically optimal.
conic visibility shortest path curved polygon planar subdivision circular visibility computational geometry ray shooting splinegon curved triangulation