查找天际线集合

Question

在讨论这个问题之前，让我先解释一些定义：

比方说点A是一个坐标(可以有两个值)，比方说(1.2,3.5,4.3,2.6)，和点B一样。

A点支配B点当且仅当1. A点中的所有坐标<= B点中的所有坐标；2. A点的一个坐标

例如:给定

A=(2,3,4,5)
B=(2,3,4,6)

A支配B，因为条件1成立，并且对于条件2，A的第四个分量

再举一个例子，

A=(2,3,4,5)
B=(2,3,4,5)

A不能支配B，反之亦然，因为条件2在两种情况下都不成立。

现在给出一个n维的坐标列表，我希望找到不受其他坐标支配的坐标集合，这些坐标称为天际线集合。

假设我有5维的坐标

(2,1,2,1,2)
(1,2,1,2,1)
(3,3,3,3,3)
(4,4,4,4,4)

天际线设置是

(2,1,2,1,2)
(1,2,1,2,1)

现在我想写一个函数：

List<double[]> SkylineSet(List<double[]> Coordinates, int dimension)

给定示例输入：

 List<double[]> newList=new List<double[]>();
 newList.Add(new double[] {2, 1, 2, 1, 2});
 newList.Add(new double[] { 1, 2, 1, 2, 1 });
 newList.Add(new double[] { 3, 3, 3, 3, 3 });
 newList.Add(new double[] { 4, 4, 4, 4, 4 });

SkylineSet(newList,5)将输出

(2,1,2,1,2)
(1,2,1,2,1)

这可以通过每个坐标的成对比较来实现，但是坐标的数量可以非常大，有人知道如何有效地解决这个问题吗？

Answer 1

将这些点放入K-D树(或类似的数据结构)中。现在，您可以高效地找到由给定点控制的点。移除那些被支配的点，对所有剩余的点重复以上步骤。

Answer 2

我不确定这是否可行。在我看来，这似乎是合理的。也可能这正是您已经在做的事情。

构建一个控制矩阵NxN，其中N是点数。矩阵中的值是“相等”、“支配”、“支配”、“都不是”。将所有矩阵单元格设置为“相等”。此矩阵保存算法结束时的结果。

从第一个坐标开始。

我在这里假设我们有一个数组，其中包含当前坐标的所有值，但也包含与它们相关的点。

建立部分支配关系，只看当前坐标。支配关系可以有以下几种值：“平等”、“被支配”、“支配”。没有“两者都没有”的说法。

在双嵌套循环中遍历此数组(I = 0，N-2；J= I+1，N-1)。给定两点的关系R和这两点的关系矩阵中的单元格C，将矩阵更新为新值C，如下所示：

如果C“相等”，则C= R。

如果C是“两者都不是”，那么它是不变的。

如果C是“支配”的，而R是“支配”的，那么C变成“两者都不”，否则是不变的。

如果C是“支配”的，而R是“支配的”，那么C变成“两者都不”，否则是不变的。

对所有坐标重复此过程，在矩阵中累积结果。

最后，对每个点运行矩阵。取所有与任何其他点没有“支配”关系的点。