Sklansky凸包算法错误原因、反例及相关依据技术问询

嘿，关于你提到的Sklansky O(n)凸包算法的错误问题，我整理了详细的信息，帮你逐一解答：

Sklansky在1972年提出的算法原本声称能以O(n)时间完成凸包计算，但它的核心逻辑存在致命漏洞：

• 算法基于贪心策略，假设在每一步构建凸包链的过程中，当前维护的链始终是凸的，仅通过局部判断（比如三点转向）来决定是否保留当前点。
• 但实际上，当点集存在特殊排列时，这种局部判断会失效——算法会错误地将属于凸包的点判定为内部点丢弃，或者把非凸包点保留下来，最终输出的结果不是正确的凸包。
• 额外的问题是，该算法的时间复杂度在最坏情况下根本达不到O(n)，实际是O(n²)，这也违背了最初的设计承诺。

有不少经典的反例可以触发算法错误，这里列举几个典型的：

• 交替折线点集：比如点按以下坐标顺序排列：(0,0)、(1,1)、(2,0)、(3,1)、(4,0)、(5,1)、(6,0)。正确的凸包应该包含(0,0)、(6,0)、(5,1)、(1,1)这四个点，但Sklansky算法会错误地保留中间的交替点，最终生成一条非凸的链，无法得到正确的凸包边界。
• 螺旋嵌套点集：一组点按螺旋形从外到内排列（或反之），当算法处理到螺旋的中间段时，会误判凸包的转向，将外层的凸包点当作内部点丢弃，导致最终无法闭合出完整的凸包。
• 凹结构带干扰点的点集：比如构造点集：A(0,0)、B(5,0)、C(5,5)、D(0,5)、E(2,3)、F(3,2)。这里E和F是内部点，但算法可能会错误地将它们加入凸包链；若调整点的输入顺序，算法甚至会把C或D这样的凸包点误判为内部点丢弃。

Sklansky算法的错误最早是由D.T. Lee和F.P. Preparata在1983年发表的论文《Worst-Case Analysis of Set Algorithms and Computational Geometry》中正式指出并证明的。他们不仅构造了类似上述的反例，还从理论上分析了算法的逻辑缺陷，证明了该算法在最坏情况下的时间复杂度为O(n²)，且无法正确处理某些点集。后续也有其他研究者补充了更多反例和分析，但Lee和Preparata是最早系统性揭露这个错误的学者。

内容的提问来源于stack exchange，提问作者code base 5000