Find a counter of all points in three-dimensional space that are strictly less than any of the points in this space?

Question

We are given n points in three-dimensional space, we need to find the count of all points that are strictly less than at least one of the points in three-dimensional space, that is.

x1<x2 and y1<y2  and z1<z2

therefore (x1, y1, z1) will be one such point.

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.

I know that this can be solved using the O (n ^ 2) algorithm, but I need something faster, I tried sorting by one dimension and then searching only for most of the key, but its still o (n ^ 2 )) the worst case.

What is an effective way to do this?

Answer 1

, , O(n^2) - .

, x, y z . , (indexes , , indexes[0] = [5,124,789] , 5- x , 124- y , 789- z- ).

- , , , , . , . .

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');

Hide result

Answer 2

, N & times; N, , :

n , Z, Y Z (n, 0,0), (0, n, 0) (0,0, ), 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 & times; N, . :

• .
• . , . , . , .
• . , . , , , . , .
• , .

, a b a lt b 25%, ( , , ).

---

(100 ) 1 000 000 , 116 ( 160), - 1 333 000 ( 2150 000).

( 10 000 000 , 11 000 000 150.)

, N, N & times; 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));

Hide result