基本上我想解决的问题的表述非常简单。给定 2 个简单多边形（没有自相交），在O(n+k)时间内报告所有相交的边对，其中 n - 是边的总数，k - 两个多边形之间的相交数。
保持在提到的时间硬度内是非常重要的。令我惊讶的是，我几乎找不到任何关于这个主题的信息。多边形相交似乎是一个自然而重要的问题。无论如何，目前我不知道是否有可能在O(n+k)中做到这一点。
可以请人帮忙解决这个问题的下限吗？
基本上我想解决的问题的表述非常简单。给定 2 个简单多边形（没有自相交），在O(n+k)时间内报告所有相交的边对，其中 n - 是边的总数，k - 两个多边形之间的相交数。
保持在提到的时间硬度内是非常重要的。令我惊讶的是，我几乎找不到任何关于这个主题的信息。多边形相交似乎是一个自然而重要的问题。无论如何，目前我不知道是否有可能在O(n+k)中做到这一点。
可以请人帮忙解决这个问题的下限吗？