A :Isunoke polygon is a closed polygonal path without self:Uintersections; a :Icrossing polygon is a closed polygonal path that may cross itself arbitrarily. It is known that the convex hull of a simply polygon can be found in :IO(:In) time, but the hull of a crossing polygon requires omega (:In log :In). Ghosh and Shyamasundar study an intermediate case suggested by Toussaint, [1]: an :Iordered corssing polygon, a crossing polygon whose hull vertices occur in the same order as they appear in the polygonal path. They present in this paper an undoubtebly clever but nearly impenetrable :IO(:In) algorithm and proof of correctness for this problem.:P They supplement their main algorithm with a :ICertification Algorithm, which is intended to detect whether the input polygon is indeed ordered; if it is not, then the output of their hull algorithm will be incorrect. Unfortunately their certification procedure is flawed in at least three ways. First, they imply that is is sufficient to check for intersections between two chains (stacks :IC and :IP in the paper) at the termination of the hull algorithm, when in fact intersection must be checked at all intermediate stages since the stacks grow and shrink during execution. This would increase the time complexity beyond linear. Second, the stack :IP can be empty even for an unordered crossing polygon, so the intersection check is not sufficient. For example, their certification procedure would erroneously pass the simplest possible unordered crossing polygon: (0,0), (2,1), (1,1), (3,0). Third, they misapply a result of Bentley, Faust, and Preparata [2], assigning linear time complexity to a step that requires omega (:In log :In). It is not surprising that testing for the ordered property of a crossing polygon is difficult since it is an open problem to check for the simplicity of a polygon in better than :IO(:In log :In).

:6HREREFENCES

:4T[1] TOUSSAINT, G. T. Computational geometric problems in pattern recognition, in :IPattern recognition theory and applications. Proc. of the NATO advanced study institute (Oxford, UK, March 29:UApril 10, 1981), J. K. Kittler, K. S. Fu and L. F. Pan (Ed.), D. Reidel Publ. Co., Hingham, MA, 1982, 73:U91. See :ICR :1A23, 7 (July 1982), Rev. 39,558. :4TBENTLEY; J. L.; FAUST, M. G.; and PREPARATA, F. P. Aproximation algorithms for conven hulls, :ICommun. ACM :1A25, 1 (Jan. 1982), 64:U68.