分治算法求解二維點集合的Skyline

實驗背景和内容

給定二維資料集合D，要求設計、分析并實作基于分治的二維資料Skyline求解算法。

思路

1. 先将所有點對都按照x軸進行排序；
2. 然後遞歸地二分所有點對；
3. 左右集合合并的時候，因為左邊集合的x值一定小于右邊集合的x值，則如果左邊的集合不為空，則依次将左邊點集的點的y值與右邊的點集中最大y值比較，如果，左邊元素的y值小于等于右邊點集中y最大的值，則左邊那個元素一定被右邊y值最大的元素所支配，就将左邊的那個點删去，直至左邊集合比較結束。
4. 然後将左邊集合加到右邊集合中，并傳回右邊的集合繼續進行遞歸。

僞代碼

Skyline(D)
1.  QuickSortByXAxis(D);
2.  SkylineDivide(D);
3.  PrintSkyline(D);

SkylineDivide(D)
1.  create arrays left ,right;
2.  if D.size>0
3.     left = D[0,mid];
4.     right = D[mid+1,r];
5.     left = SkylineDivide(left);
6.     right = SkylineDivide(right);
7.     D = SkylineConquerMerge(left,right);
8.  return D;

SkylineConquerMerge(left,right)
 1.  ryMax = Max(right)
 2.  for j ← 0 to left.size
 3.     p = left[j];
 4.      if (p.Y <= ryMax.Y)
 5.        left.remove(p);
 6.  right.addAll(left);
 7.   return right;
           

性能分析

• Skyline(D)的第1行對所有點進行排序，快排的時間複雜度是T(n)=θ(nlgn)；
• SkylineDivide(D)的第5、6行對所有點進行二分，第7行進行合并，合并的時間複雜度是θ(n)；
• 是以我麼可以得到SkylineDivide(D)函數的時間複雜度是T(n)=T(n/2)+θ(n)，根據master定理，可知T(n)=θ(nlgn)；
• 是以，skyline的分治算法的時間複雜度為T(n)=θ(nlgn)+θ(nlgn)=θ(nlgn)。

結果

skyline問題的Java源代碼