查找天际线套装 [英] Finding Skyline Set
问题描述
让我才去的问题，只是解释一些定义：
Let me just explain some definition before going to the problem:
说点A为坐标（可能有双重价值），说（1.2,3.5， 4.3,2.6），
同样到b点。
Say point A is a coordinates(that could have double value), say (1.2,3.5,4.3,2.6), same to point B.
一个点一个点占主导地位b，
当且仅当
1.在所有坐标点A< = b点所有的坐标，和
2.一个点A<的协调;对应的点B
A point A dominates point B, iff 1. all coordinates in point A <= all coordinates in point B, and 2. one coordinate of point A < corresponding coordinates of point B
例如：考虑到
For example: Given
A=(2,3,4,5)
B=(2,3,4,6)
A胜过b时，由于条件1成立，并为条件2，A<的第四部分;第四组分B
A dominates B since condition 1 holds, and for condition 2, the forth component of A < forth component of B.
由于另一个例子，
A=(2,3,4,5)
B=(2,3,4,5)
无论是A胜过b，反之亦然，因为条件2并不在这两种情况下举行。
Neither A dominates B, and vice versa, since condition 2 does not hold in both cases.
现在给定的n维坐标的名单，我想找到一组不受他人支配的坐标，
这些坐标被称为天际线集。
Now given a list of coordinate of n dimension, I wish to find the set of coordinates that are not dominated by others, these coordinates are termed as skyline set.
说我有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)
现在我想编写一个函数：
Now I wish to write a function:
List<double[]> SkylineSet(List<double[]> Coordinates, int dimension)
鉴于例如输入：
Given example input:
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)
这可以由每个坐标两两比较实现的，但是坐标的
号即可非常大，任何一个有想法如何有效地解决这个？
This could be achieved by pairwise comparison of each coordinates, but the number of coordinates can be very large, any one has idea how to solve this efficiently?
推荐答案
放在一个KD树（或者点一些这样的数据结构）。现在，你可以有效地找到一个给定的点为主的点。删除那些得到为主，重复所有剩余的点。
Put the points in a K-D tree (or some such data structure). Now, You can efficiently find points dominated by a given point. Remove those that got dominated, repeat for all remaining points.
这篇关于查找天际线套装的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
