Characterizing LR-visibility polygons and related problems

Bhattacharya, Binay K. ; Ghosh, Subir Kumar (2001) Characterizing LR-visibility polygons and related problems Computational Geometry, 18 (1). pp. 19-36. ISSN 0925-7721

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1016/S0925-7721(00)00024-9

Abstract

A simple polygon P is said to be LR-visibility polygon if there exists two points s and t on the boundary of P such that every point of the clockwise boundary of P from s to t (denoted as L ) is visible from some point of the counterclockwise boundary of P from s to t (denoted as R) and vice versa. In this paper we derive properties of shortest paths in LR-visibility polygons and present a characterization of LR visibility polygons in terms of shortest paths between vertices. This characterization suggests a simple algorithm for the following recognition problem. Given a polygon P with distinguished vertices s and t, the problem is to determine whether P is a LR-visibility polygon with respect to s and t. Our algorithm for this problem checks LR-visibility by traversing shortest path trees rooted at s and t in DFS manner and it runs in linear time. Using our characterization of LR-visibility polygons, we show that the shortest path tree rooted at a vertex or a boundary point can be computed in linear time for a class of polygons which contains LR-visibility polygons as a subclass. As a result, this algorithm can be used as a procedure for computing the shortest path tree in our recognition algorithm as well as in the recognition algorithm of Das, Heffernan and Narasimhan. Our algorithm computes the shortest path tree by scanning the boundary of the given polygon and it does not require triangulation as a preprocessing step.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Visibility; Euclidean Shortest Path; Shortest Path Tree; Merging
ID Code:76280
Deposited On:31 Dec 2011 08:57
Last Modified:31 Dec 2011 08:57

Repository Staff Only: item control page