ISSN:
1432-0541
Keywords:
Computational geometry
;
Simple polygon
;
Visibility
;
Linear-time algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygonP are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are described. For a convex-chain visibility problem, two linear-time algorithms are exhibited for determining whether or notP is visible from a given convex chain; one is the turn-checking approach and the other is the decomposition approach based on checking edge visibilities. We also present a linear-time algorithm for finding, if any, all maximal convex chains of a given polygonP from whichP is visible, where a maximal convex chain is a convex chain which does not properly include any other convex chains. It can be made by showing that there can be at most four visible maximal convex chains inP with an empty kernel. By similar arguments, we show that the same problems for reflex chain visibility can be easily solved in linear time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01840400
