基本上我想解决的问题的表述非常简单。给定 2 个简单多边形（没有自相交）在O(n+k)时间内报告所有相交的边对，其中 n - 是边的总数，k - 两个多边形之间的相交数。
保持在提到的时间硬度内是非常重要的。令我惊讶的是，我几乎找不到关于这个主题的信息。多边形相交似乎是一个如此自然而重要的问题。无论如何，目前我不知道是否有可能在O(n+k)中做到这一点。
可以请人帮忙解决这个问题的下限吗？
关于我的问题的一些额外观点：
- 使用集合操作和相交报告（关于我的问题）进行多边形裁剪似乎是稍微不同的问题 - 找到相交边后，您将不得不收缩一个多边形，这是裁剪/集合操作的结果。
- 基于段相交算法的方法对我不起作用。事实证明，最坏的情况需要 O(nlogn+k)。
- 我并不是坚持存在具有这种硬度的算法——它可能不存在。但在这种情况下，如果有人能为我的问题提供下限证明，我将不胜感激 - 大量论文提供了一些非常有趣的算法（通常具有 O(nlogn+k) 复杂度），但由于某种原因没有提及下限.