在三维空间中查找所有点的数量，这些点严格小于该空间中任何点的值？

Question

在三维空间中查找所有点的数量，这些点严格小于该空间中任何点的值？

4

我们在三维空间中给定了n个点，需要找出所有严格小于三维空间中至少一个点的所有点的数量，即：

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)。

有没有更有效的方法？

- A. Sam

“less”是什么意思？(1,5,2) < (2,4,2)吗？你的意思是最靠近原点，就像d^2 = x^2+y^2+z^2并比较距离d吗？ - John Alexiou

2个回答

0

我怀疑最坏情况的复杂度无法降低到N×N以下，因为可以创建输入，其中没有一个点严格小于任何其他点：

对于任何值n，考虑与Z轴、Y轴和Z轴相交于(n,0,0)、(0,n,0)和(0,0,n)的平面，由方程x+y+z=n描述。如果输入由这样的平面上的点组成，则没有任何一个点严格小于任何其他点。

最坏情况输入的示例：

(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)

然而，平均复杂度可以降低到远远小于N×N，例如采用以下方法：

从输入中取出第一个点并将其放入列表中。
从输入中取出第二个点，并将其与列表中的第一个点进行比较。如果它严格小于，则丢弃新点。如果它严格大于，则用新点替换列表中的点。如果两者都不是，则将该点添加到列表中。
对于来自输入的每个新点，将其与列表中的每个点进行比较。如果它严格小于列表中的任何点，则丢弃新点。如果它严格大于，则用新点替换列表中的点，并且丢弃严格小于新点的任何进一步点。如果新点既不严格小于也不严格大于列表中的任何点，则将新点添加到列表中。
在检查输入中的每个点之后，结果是输入中的点数减去列表中的点数。

由于对于任意两个随机点a和b，a<b或b<a的概率为25％，因此列表不会变得非常大（除非输入被特别制作为包含几乎没有严格小于任何其他点的点）。

以下代码的有限测试（100个案例），在一个立方空间中随机分布了1,000,000个点，结果显示平均列表大小约为116（最大值为160），检查一个点是否严格小于另一个点的次数约为1,333,000次（最大值为2,150,000次）。 （对10,000,000个点进行了一些测试，结果显示平均检查次数约为11,000,000次，列表大小约为150。） 因此，在实践中，平均复杂度接近于N而不是N×N。

function xyzLessCount(input) {
    var list = [input[0]];                                // put first point in list
    for (var i = 1; i < input.length; i++) {              // check every point in input
        var append = true;
        for (var j = 0; j < list.length; j++) {           // against every point in list
            if (xyzLess(input[i], list[j])) {             // new point < list point
                append = false;
                break;                                    // continue with next point
            }
            if (xyzLess(list[j], input[i])) {             // new point > list point
                list[j] = input[i];                       // replace list point
                for (var k = list.length - 1; k > j; k--) {
                    if (xyzLess(list[k], list[j])) {      // check rest of list
                        list.splice(k, 1);                // remove list point
                    }
                }
                append = false;
                break;                                    // continue with next point
            }
        }
        if (append) list.push(input[i]);                  // append new point to list
    }
    return input.length - list.length;

    function xyzLess(a, b) {
        return a.x < b.x && a.y < b.y && a.z < b.z;
    }
}

var points = [];                                          // random test data
for (var i = 0; i < 1000000; i++) {
    points.push({x: Math.random(), y: Math.random(), z: Math.random()});
}
document.write("1000000 &rarr; " + xyzLessCount(points));

- m69 ''snarky and unwelcoming''

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

有一种优化搜索的方法，可能比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');