3次元空間内のすべての点の数が、その空間内のどの点よりも厳密に小さいか調べます。

Question

我々3D空間に与えられたn個の点で、我々は

x1<x2 and y1<y2 and z1<z2 

すなわち3D空間 の点の少なくとも1つのより厳密に小さいすべてのポイントの数を見つける必要があるので、（X1、Y1、Z1 ）そのようなポイントの1つになります。

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）のアルゴリズムが、私はより高速なものが必要で、私は1つの次元をソートし、キーの大部分の上にのみ検索しようとしたが、そのまだO （n^2）最悪の場合。

効率的な方法は何ですか？

Answer 1

私はない点は、任意の他の点よりも厳密に小さいされていない場合、入力を作成することが可能であるので、最悪の場合の複雑さは、N × N未満に低減することができることを疑う：任意の値について

N式 x + y + z = 0で表される、（n、0,0）、（0、n、0）および（0,0、n）におけるZ、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、例えばよりもはるかに小さいとすることができますこのアプローチでは：

• 入力から最初のポイントを取り出してリストに入れます。
• 入力から2番目のポイントを取り出し、リストの最初の ポイントと比較します。厳密に少ない場合は、新しいポイントを破棄します。 厳密に大きい場合は、リスト内のポイントを新しい ポイントに置き換えます。同じでない場合は、ポイントをリストに追加します。
• 入力の新しいポイントごとに、 リストの各ポイントと比較します。それがリスト内のどのポイントよりもはるかに小さい場合は、 新しいポイントを破棄します。厳密にそれより大きい場合は、リスト のポイントを新しいポイントに置き換えます。また、新しいポイントよりも厳密に小さいリスト のそれ以上のポイントは破棄します。新しいポイントが ではなく、リスト内のポイントより厳密に小さいか大きい場合は、新しい ポイントをリストに追加します。
• 入力のすべてのポイントを確認した後、結果は入力の ポイントの数からリストのポイント数を差し引いた数になります。

確率は、任意の2つのランダムな点についてと Bいずれか< B又はB < Aが25％であるので、入力は具体的でない限り、リストは、（非常に大きいことが成長しないであろう厳密には他のポイントよりも少ない点をほとんどまたは全く含まないように作られている）。立方空間内1,000,000ランダムに分布点で以下のコード（100例）と

---

限定テストは平均リストサイズは約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));

Answer 2

よりも速いかもしれ検索を最適化する方法があります- カウンターサンプルの入力を歓迎します。

x、y、zでそれぞれソートされたポイントのインデックスの3つのリストを保持します。それぞれのリストを各リストと関連付けた4番目のリストを作成します（、例：indexes[0] = [5,124,789]）。最初のポイントはxソート済みリストの5番目、yソート済みリストの124番目、789番目zソートされたリスト）。

ポイントを反復する - ポイントが最も高いリストを選択し、リスト内のより高いインデックスされたポイントに対してポイントをテストします。ポイントが厳密に1つ未満の場合は早めに終了します。 3つのリストすべてでポイントが低い場合は、厳密に高いポイントを見つける可能性が高くなります。それ以外の場合は、リストの1つが高いほど反復回数が少なくなります。

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