Computing the visibility polygon from a convex set and related problems

Ghosh, Subir Kumar (1991) Computing the visibility polygon from a convex set and related problems Journal of Algorithms, 12 (1). pp. 75-95. ISSN 0196-6774

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/0196-6774(91)90024-S

Abstract

In this paper, we propose efficient algorithms for computing the complete and weak visibility polygons of a simple polygon P of n vertices from a convex set C inside P. The algorithm for computing the complete visibility polygon of P from C takes O(n + k) time in the worst case, where k is the number of extreme points of the convex set C. Given a triangulation of P - C, the algorithm for computing the weak visibility polygon of P from C takes O(n + k) time in the worst case. We also show that computing the complete and weak visibility polygons of P from a nonconvex set inside P has the same time complexity. The algorithm for computing the complete visibility polygon of P from a convex set inside P leads to efficient algorithms for the following problems: (i) Given a polygon Q of m vertices inside another polygon P of n vertices, construct a minimum nested convex polygon K between P and Q. The algorithm runs in O((n + m)log k) time, where k is the number of vertices of K. This is an improvement over the O((n + m)log(n + m)) time algorithm of Wang and Chan. (ii) Given two points inside a polygon P, compute a minimum link path between them inside P. Given a triangulation of P, the algorithm takes O(n) time. Suri also proposed a linear time algorithm for this problem in a triangulated polygon but our algorithm is simpler.

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

Repository Staff Only: item control page