ISSN:
1432-2315
Keywords:
Visibility
;
Polygon
;
Weak visibility
;
Convex hull
;
Hidden line problems
;
Monotone polygons
;
Jordan sorting
;
Computational geometry
;
Graphics
;
Algorithms
;
Geometric complexity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract One of the most recurring themes in many computer applications such as graphics automated cartography, image processing and robotics is the notion of visibility. We are concerned with the visibility between two edges of a simplen-vertex polygon. Four natural definitions of edge-to-edge visibility are proposed. There existO(nlogn) algorithms and complicatedO(nlog logn) algorithms to solve this problem partially and indirectly. A linear running time, and thus optimal algorithm is presented to determine edge-to-edge visibility under any of the four definitions. This simple, efficient, and direct algorithm without computing the triangulation of the simple polygon also identifies the visibility region if it exists.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01952419
Permalink
