Finding the convex hull of a simple polygon in linear time (Q1096406)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Finding the convex hull of a simple polygon in linear time |
scientific article |
Statements
Finding the convex hull of a simple polygon in linear time (English)
0 references
1986
0 references
Though linear algorithms for finding the convex hull of a simply- connected polygon have been reported, not all are short and correct. A compact version based on \textit{J. Sklansky}'s original idea [IEEE Trans. Comput. C-21, 1355--1364 (1972; Zbl 0247.68046)] and \textit{A. Bykat}'s counterexample [Inf. Process. Lett. 7, 296--298 (1978; Zbl 0392.52002)] is given. Its complexity and correctness are also shown.
0 references
computational geometry
0 references
linear algorithms
0 references
convex hull
0 references
simply-connected polygon
0 references
