algorithm - 使用动态规划寻找最大区间

Question

http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf 我在练习这些问题时遇到了一个难倒我的问题。

7.(a) Suppose we are given a set L of n line segments in the plane, where each segment has one endpoint on the line y = 0 and one endpoint on the line y = 1, and all 2n endpoints are distinct. Describe and analyze an algorithm to compute the largest subset of L in which no pair of segments intersects.

(b) Suppose we are given a set L of n line segments in the plane, where the endpoints of each segment lie on the unit circle x 2 + y 2 = 1, and all 2n endpoints are distinct. Describe and analyze an algorithm to compute the largest subset of L in which no pair of segments intersects.

我想出了如何在 O(n log n) 时间内完成 7a，(这个问题是一个变相的问题，寻找递增数字的最大子集)。我几乎要放弃 7b，因为我想不出办法。

但是，有没有办法将 7b 的前提转换为更像 7a 的前提？我觉得这是解决问题的正确方法，非常感谢任何帮助解决这个问题的方法。

Answer 1

我想不出一个 O(n*log(n)) 的算法，但这是一个 O(n²) 的算法。

我们的想法是构建一个有向图，其中顶点代表给定集合中的片段，边代表“位于右侧”的关系。

令 L 为段列表:{(a₁, b₁), (a₂, b₂ ), ..., (a_n, b_n)}，其中 a_k 和 b_k 是第 k 个段的端点。

令 L' 为片段列表:{(a₁, b₁), (b₁, a ₁), (a₂, b₂), (b₂, a₂) , ..., (a_n, b_n), (b_n, a_n)}。

设图的顶点有从 1 到 2*n 的索引，每个索引 k 代表线段 L'[k]，即 (a_k/2, b_k/2) 如果 k 是奇数，并且 (b_k/2, a_k/2) 如果 k 是偶数。

线段 (a₁, b₁) 位于线段 (a₂, b _的右侧>2) 当点a₁, a₂, b₂, b₁是在单位圆上按顺时针方向排列。

请注意 1) 如果一条线段位于另一条线段的右侧，则它们不会相交； 2) 如果来自 L 的两条线段不相交，则来自 L' 的四个对应线段中的两条必然位于另一条线段的右侧； 3) 来自 L 的任何一组非相交线段由 L' 的一系列线段定义，每个线段位于前一个线段的右侧。

算法概要:

for every k1 from 1 to 2*n:
    for every k2 from 1 to 2*n:
        if (L'[k1].a, L'[k1].b) lies to the right of (L'[k2].a, L'[k2].b):
            add a directed edge (k1, k2) to the graph 
Find the longest path in the graph: (k1, k2, ..., km). 
The answer to the problem is: (k1/2, k2/2, ..., km/2).