Characterizing and recognizing weak visibility polygons

Ghosh, Subir Kumar ; Maheshwari, Anil ; Pal, Sudebkumar Prasant ; Saluja, Sanjeev ; Veni Madhavan, C. E. (1993) Characterizing and recognizing weak visibility polygons Computational Geometry, 3 (4). pp. 213-233. ISSN 0925-7721

Full text not available from this repository.

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

Related URL: http://dx.doi.org/10.1016/0925-7721(93)90010-4

Abstract

A polygon is said to be a weak visibility polygon if every point of the polygon is visible from some point of an internal segment. In this paper we derive properties of shortest paths in weak visibility polygons and present a characterization of weak visibility polygons in terms of shortest paths between vertices. These properties lead to the following efficient algorithms: (i) an O(E) time algorithm for determining whether a simple polygon P is a weak visibility polygon and for computing a visibility chord if it exist, where E is the size of the visibility graph of P and (ii) an O(n2) time algorithm for computing the maximum hidden vertex set in an n-sided polygon weakly visible from a convex edge.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:76275
Deposited On:31 Dec 2011 08:56
Last Modified:31 Dec 2011 08:56

Repository Staff Only: item control page