Finding the convex hull of a simple polygon in linear time (Q1096406): Difference between revisions

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.