Abstract
A frequently used algorithm for finding the convex hull of a simple polygon in linear running time has been recently shown to fail in some cases. Due to its simplicity the algorithm is, nevertheless, attractive. In this paper it is shown that the algorithm does in fact work for a family of simple polygons known as weakly externally visible polygons. Some application areas where such polygons occur are briefly discussed. In addition, it is shown that with a trivial modification the algorithm can be used to internally and externally triangulate certain classes of polygons in 0(n) time.
Original language | English (US) |
---|---|
Pages (from-to) | 23-29 |
Number of pages | 7 |
Journal | Pattern Recognition |
Volume | 15 |
Issue number | 1 |
DOIs | |
State | Published - 1982 |
Keywords
- Algorithm
- Computational complexity
- Computational geometry
- Convex hull
- Image processing
- Pattern recognition
- Simple polygon
- Triangulation Polygon decomposition
- Weakly externally visible polygon
ASJC Scopus subject areas
- Software
- Signal Processing
- Computer Vision and Pattern Recognition
- Artificial Intelligence