是否存在O(logN)时间复杂度的凸包最左侧点删除算法？

结论很明确：不存在最坏情况下时间复杂度不超过O(logN)的最左侧点删除算法。

原因如下：

• 凸包的结构由所有点的相对位置共同约束，最左侧点作为凸包的左端点，它的存在可能支撑着后续一段凸包边缘。一旦删除它，原本依赖这个点的凸边可能完全失效，必须重新验证从新左端点开始的一系列点的凸性。
• 举个极端场景：所有点都在上凸包上，从左到右y值严格递减，形成一条“下坡”折线。此时删除最左侧点后，新的左端点到下一个点的边，需要和后续所有点逐一判断是否满足凸包的左转/右转条件，这个过程必须遍历O(N)个点才能完成，根本没法用O(logN)的时间搞定。
• 从计算几何的理论下界来看，这类动态凸包维护问题中，左侧删除操作的最坏时间复杂度下界就是Ω(N)，目前没有任何算法能突破这个限制。

补充一句：如果是**均摊O(logN)**时间的话，确实有一些基于平衡树、分层结构的动态凸包数据结构能做到，但这类结构只能保证多次操作后的平均复杂度，单次删除的最坏情况还是会落到O(N)。但如果要求单次删除的最坏情况必须是O(logN)，目前没有已知的可行算法。

内容的提问来源于stack exchange，提问作者Egor