c# - 查找天际线集

在讨论这个问题之前，让我先解释一下定义：
比如说点A是一个坐标（可能有两个值），比如说（1.2,3.5,4.3,2.6）。
与B点相同。
A点支配B点，
敌我识别
一。A点的所有坐标2.A点的一个坐标例如：
鉴于

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

由于条件1成立，a支配b，对于条件2，a的第四个分量再举一个例子，

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

由于条件2在两种情况下都不成立，所以a都不支配b，反之亦然。
现在给出一个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)

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

最佳答案

把这些点放在一个k-d树（或一些这样的数据结构）中。现在，您可以有效地找到由给定点支配的点。去掉那些被控制的，重复所有剩余的点。