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