A Unified Approach to Conic Visibility |
| |
Authors: | J. García-López P. A. Ramos |
| |
Affiliation: | (1) Departamento de Matemática Aplicada, E. U. Informática, Universidad Politécnica de Madrid, Ctra. Valencia Km 7, 28031 Madrid, Spain. jglopez@eui.upm.es., ES;(2) Departamento de Matemáticas, Universidad de Alcalá, Apto. Correos 20, 28871 Alcalá de Henares, Madrid, Spain. pedro.ramos@uah.es., ES |
| |
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.} Received August 21, 1997; revised December 27, 1998. |
| |
Keywords: | . Computational geometry Planar subdivision Shortest path Ray shooting Curved polygon Splinegon Curved triangulation Circular visibility Conic visibility. |
本文献已被 SpringerLink 等数据库收录! |
|