关于Lee-Preparata多边形核算法O(n)时间复杂度的疑问

• 核心：全局总遍历次数的线性约束
  你误解了论文中复杂度描述的范围——作者提到的：

  "the total number of vertices visited by the algorithm in handling case (1.1), is bounded above by 3n, i.e. it is O(n)"
  是处理所有顶点的总访问次数，而非单次交集计算的次数。

• 关键优化：遍历状态的复用
  算法维护的区域K是一个逐步收缩的凸多边形（或半平面交集），每次处理顶点时，并非从头遍历K的所有边。它通过指针记录上一次处理后K的有效边界位置，后续操作仅从该位置继续遍历，避免重复访问已处理过的边。这种单向的、状态复用的遍历方式，使得所有顶点处理过程中，K的边被访问的总次数严格控制在O(n)级别。

• 无核提前终止的角色
  你提到的额外测试确实用于无核场景下提前终止，但这只是辅助优化，算法的线性复杂度核心在于全局总遍历次数的线性约束，即使多边形存在核，总操作次数依然不会超过O(n)。

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