algorithm - 查找 3d 空间中严格小于该空间中任何点的所有点的计数？

Question

我们在 3d 空间中给定 n 个点，我们需要找到严格小于 3d 空间中至少一个点的所有点的计数即

x1<x2 and y1<y2  and z1<z2

所以 (x1,y1,z1) 就是这样一个点。

For example,Given points

1 4 2
4 3 2
2 5 3


(1,4,2)<(2,5,3)

So the answer for the above case should be the count of such points i.e. 1.

我知道这可以通过 O(n^2) 算法解决，但我需要更快的东西，我尝试通过一维排序，然后只搜索键的大部分，但它仍然是 o(n^2 ) 最坏的情况下。

执行此操作的有效方法是什么？

Answer 1

有一种方法可以优化您的搜索，它可能比 O(n^2) 更快 - 我欢迎反样本输入。

保留三个点的索引列表，分别按 x、y 和 z 排序。制作第四个列表，将每个点与其在每个列表中的位置相关联(下面代码中的 indexes；例如，indexes[0] = [5,124,789] 表示第一个点在 x 排序列表中排在第 5 位，在 y 排序列表中排在第 124 位，在 z 排序列表中排在第 789 位。

现在遍历点 - 选择点最高的列表并针对列表中较高索引的点测试该点，如果该点严格小于其中之一，则提前退出。如果一个点在所有三个列表中都较低，则找到严格更高点的可能性更大。否则，其中一个列表中较高的位置意味着较少的迭代。

JavaScript 代码:

function strictlyLessThan(p1,p2){
  return p1[0] < p2[0] && p1[1] < p2[1] && p1[2] < p2[2];
}

// iterations
var it = 0;

function f(ps){
  var res = 0,
      indexes = new Array(ps.length);
  
  // sort by x
  var sortedX = 
        ps.map(function(x,i){ return i; })
          .sort(function(a,b){ return ps[a][0] - ps[b][0]; });
  
  // record index of point in x-sorted list
  for (var i=0; i<sortedX.length; i++){
    indexes[sortedX[i]] = [i,null,null];
  }
  
  // sort by y
  var sortedY = 
        ps.map(function(x,i){ return i; })
          .sort(function(a,b){ return ps[a][1] - ps[b][1]; });
  
  // record index of point in y-sorted list
  for (var i=0; i<sortedY.length; i++){
    indexes[sortedY[i]][1] = i;
  }
  
  // sort by z
  var sortedZ = 
        ps.map(function(x,i){ return i; })
          .sort(function(a,b){ return ps[a][2] - ps[b][2]; });
  
  // record index of point in z-sorted list
  for (var i=0; i<sortedZ.length; i++){
    indexes[sortedZ[i]][2] = i;
  }
  
  // check for possible greater points only in the list
  // where the point is highest
  for (var i=0; i<ps.length; i++){
    var listToCheck,
        startIndex;
    
    if (indexes[i][0] > indexes[i][1]){
      if (indexes[i][0] > indexes[i][2]){
        listToCheck = sortedX;
        startIndex = indexes[i][0];
      } else {
        listToCheck = sortedZ;
        startIndex = indexes[i][2];
      }
      
    } else {
      if (indexes[i][1] > indexes[i][2]){
        listToCheck = sortedY;
        startIndex = indexes[i][1];
      } else {
        listToCheck = sortedZ;
        startIndex = indexes[i][2];
      }
    }
    
    var j = startIndex + 1;
 
    while (listToCheck[j] !== undefined){
      it++;
      var point = ps[listToCheck[j]];
 
      if (strictlyLessThan(ps[i],point)){
        res++;
        break;
      }
      j++;
    }
  }
  
  return res;
}

// var input = [[5,0,0],[4,1,0],[3,2,0],[2,3,0],[1,4,0],[0,5,0],[4,0,1],[3,1,1], [2,2,1],[1,3,1],[0,4,1],[3,0,2],[2,1,2],[1,2,2],[0,3,2],[2,0,3], [1,1,3],[0,2,3],[1,0,4],[0,1,4],[0,0,5]];

var input = new Array(10000);

for (var i=0; i<input.length; i++){
  input[i] = [Math.random(),Math.random(),Math.random()];
}

console.log(input.length + ' points');
console.log('result: ' + f(input));
console.log(it + ' iterations not including sorts');