ISSN:
1432-0541
Keywords:
Key words. Computational geometry, Planar subdivision, Shortest path, Ray shooting, Curved polygon, Splinegon, Curved triangulation, Circular visibility, Conic visibility.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. {In this paper we present linear time algorithms for computing the shortest path tree from a point and the weak visibility polygon of an arc 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 arc, such that each face of the subdivision corresponds to rays hitting the same arc 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.}
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004530010042
Permalink
