"top hull"有什么有效的算法吗？

Question

例如，当点在 x,y 坐标中以 (x-left, x-right, y) 的形式给出时，( 1 , 5 , 3), (2 , 4, 5) returns (1,2,3) , (2 ,4 ,5), (4,5,3)

Answer 1

一个简单的贪心算法巧妙地解决了这个问题。按 y 坐标降序对您的细分进行排序；约；；此列表 seg。现在...

top_hull = [empty set]
while seg is not empty
    head = seg.pop()    // pop off the highest segment.
    top_hull += head
    for each segment in seg
        remove the interval (head.xleft, head.y-left) from segment

请注意，在某些情况下可以删除间隔：

`head`'s interval does not overlap `segment`
    no action
`head`'s interval contains `segment`
    remove segment
`segments`'s interval contains `head` (both ends stick out
    split segment into the two remaining pieces.
`head`'s interval overlaps one end of `segment`
    truncate segment

根据您的实现语言，区间代数可能有出色的支持包。

Answer 2

Prunes answer 的想法是正确的，但我觉得解释如何检查间隔重叠并不公平。事实上，算法的那部分以二次时间 O(n^2) 运行，因为它在某个点形成所有 n^2 对，这是不必要的。我会做什么-

正在排队

首先，从您的段列表创建一个最大堆，以 y 坐标作为其键。您可以在 O(logn) 时间内提取和删除最大值，因此这与排序的时间复杂度相同，只是内置弹出。

heap = max_heap(segement_list)
output = []
while heap is not empty
    segment = heap.pop() # max / highest

    # trim / split segment
    # append trimmed segment(s)

十字路口

现在我们只需要 trim 段。我们将使用另一种数据结构来允许我们快速查询潜在的交叉点，而不是将它与其他所有段配对并 trim 根据需要进行匹配。我们会将每个添加的段存储在二叉搜索树中，以较低的 x 坐标作为其键。然后我们可以遍历这棵树，寻找小于或等于我们要添加的线段的最大线段（按较低的 x 坐标）。

为了让下面的段落不那么臃肿的技术细节，让我们先把两个关键比较的实现细节去掉。假设段 a 具有比 b 更小的 lower_x 值（因为在接下来的段落中，我们将始终知道哪个更小）。

# boolean- do `a` and `b` intersect
function intersects(a, b)
    return a.upper_x >= b.lower_x

# boolean- is `b` a subsegment of `a`
function is_subsegment(a, b)
    return a.upper_x >= b.upper_x

我们还需要三个转换，使用相同的 a 和 b 定义 -

function merge(a, b)
    a.upper_x = b.upper_x

function trim_left(a, b)
    a.upper_x = b.lower_x

function trim_right(a, b)
    b.lower_x = a.upper_x

回到查询BST的想法——取left_segment查询我们的段segment时得到的，看看它们是否相交。如果它们相交，检查是否 segment is_subsegment of left_segment。如果是，则中止并 continue 进入堆中的下一个段。否则，只要它们相交，我们就需要 trim_right segment。无论是否有交集，我们都会处理任何右侧的交集。之后，如果它们重叠，我们可以 merge 修改后的 segment（实际上是 subsegment，如您所见）和 left_segment。

left_segment 是唯一可以从左侧重叠的片段，因为我们在将所有重叠片段插入 BST 时合并它们。然而，这不适用于右侧，因为我们的 segment 尚未从右侧 trimmed。我们需要逐步处理 trimming。

取right_segment作为树中left_segment之后的下一段（中序遍历）。复制一份名为 subsegment 的 segment。如果 subsegment 与 right_segment 相交，trim_left 它，将 subsegment 插入输出数组，合并两个段，并从 BST 中删除 right_segment。否则，只需将 subsegment 插入数组即可。现在我们可以合并 subsegment 和 left_segment，如果它们重叠的话。如果没有，则将 subsegment 插入 BST，并将变量 left_segment 赋给它。

现在我们重复这个过程，直到我们从 segment 突破成为 left_segment 的 is_subsegment。之后，我们用堆中的下一段重复整个过程。

分析

我们知道形成最大堆并弹出最大 n 次将导致 O(nlogn) 时间复杂度。棘手的部分是计算出处理交叉点的时间复杂度。观察到对于我们处理的每个段，在处理和合并所有 subsegment 之后，我们将 BST 整体的大小最多增加一个。这是因为我们所有的 subsegment 每次迭代都会合并在一起，所以它们最终形成了一个大段。这意味着我们的 BST 不大于 n，因此查询和删除/插入 BST 需要 O(logn) 时间。

另请注意，对于插入到 BST 中的每个段，它只会与另一个段相交一次 - 因为当它这样做时，两个（或更多）将合并为一个新的段。例外情况是当一个段是其 left_segment 的子段时，但在这种情况下我们中止而不发出任何新段，因此它的 +0 大小净变化无论如何。利用这一知识，结合之前的观察，即每个片段最终最多为 BST 贡献一个新片段，我们可以得出结论，最多会有 O(n) 个交集，因此会有插入/删除。所以 O(nlogn) 是时候维护我们的 BST 了。

考虑到我们其余的操作都是常数时间，我们的整体时间复杂度是 O(nlogn)，而不是 O(n^2) 当暴力破解交叉点和 trimming.

Answer 3

解决此问题的最简单高效（O(N log N)）方法是使用 "line sweep" 算法。

想象一下，在整个集合中从左到右扫过一条垂直线，跟踪它穿过的最上面的线段。每当最顶部的部分发生变化时，这是一个可能影响顶部船体的重要事件。从这些变化的列表中可以很容易地计算出顶壳。

请注意，这些重要事件只能发生在其中一个输入段开始或结束的 x 位置。因此，我们无需平滑地扫过直线，只需考虑在这些 x 位置发生的情况。所以：

生成段的所有开始和结束事件的列表。例如，对于段 { 1, 2, 5} 会生成事件 {1, start 5}, {2, end 5}
创建最大堆以跟踪最顶部的段。
将所有事件按x位置排序，并按顺序处理。对于具有相同 x 位置的事件，首先执行开始事件。这确保您在每个片段的结束事件之前处理每个片段的开始事件。
对于列表中的每个x位置，处理以该x位置为单位的所有事件。对于每个开始事件 {x, start y} 将 y 添加到堆中。对于每个事件 {x, end y}，从堆中移除 y。
处理完 x 位置的事件后，堆中最大的元素是顶壳的 y 位置，直到列表中的下一个 x 位置。

"top hull"有什么有效的算法吗？

Are there any efficient algorithm for "top hull"?

algorithm

divide-and-conquer

convex-hull

正在排队

十字路口

分析