3.1 対数法に基づくアルゴリズム
最初のアルゴリズムは、Bentleyの対数法の適用に基づくものである 。 この応用はSmidに初めて登場した。 (Schwarz も参照)
SをℝDの現在の点集合とし、nをその大きさとする。 nを2進数で書くと、n=∑i≧0ai2i、ここでai∈{0,1}とする。 Sを（任意に）部分集合に分割する：ai = 1となる各iに対して、サイズ2iの部分集合Siが1つ存在する。 さらに、そのような各iに対して、d（S）≦δi ≦d（Si） となる実数δi が存在する。
(1)
Sの最も近いペアとその距離δ
(2)
ai=1となる各iに対して、Siの点を保存したδi -grid が存在する。 このグリッドの空でないセルは平衡二分探索木に格納され、それらの「左下」角に従って辞書式にソートされていると仮定する。
ここで新しい点pの挿入を考える。ai = 1である各iについて、pと3D – 1隣接セルが含まれているδiグリッドのセルを見つける。 そして、pとこれらのセルに含まれるSiのすべての点との間の距離を計算する。 もしδより小さい距離があれば、δを更新し、最も近いペアを更新する。 あとはデータ構造の残りの部分を更新する。 a0 = a1 = … = aj – 1 かつ aj = 0 となるインデックスを j とすると、Sj := {p} となる。 ∪ S0 ∪ S1 ∪ … ∪ Sj – 1、δj :=δである。 集合Sjに対してδj-グリッドを構築し、集合S0、S1、…Sj – 1に対してグリッドを破棄する（これにより、これらの集合を暗黙的に空にする）。
このアルゴリズムの正しさを証明するには、d（S） ≦ δiなので、pとpの近隣- δiグリッド内にあるSiのすべての点を比較すれば十分であることに注意する。 したがって、最も近いペアは正しく更新される。 また、新しい値Sjは、d（S∪｛p｝）≦δj≦d（Sj）を満たし、すべてのi＜3606＞jについて、d（S∪｛p｝≦δi d（Si）が成立する。 最後に、更新されたデータ構造には、n＋1の2進表現が位置iに1を含むような各iについて2i点を格納するグリッドが含まれる。
挿入アルゴリズムの複雑さを分析する。 まず、δi ≦ d(Si)であるから、δi -グリッドにおけるpの近傍はSiの点の最大一定数しか含まないことに注意。 したがって、各グリッドに対してO(log n)の時間を費やすことになる。 データ構造はグリッドの対数数を含むので、挿入アルゴリズムの最初の部分はO（log 2n）時間を要する。
アルゴリズムの2番目の部分、δj -グリッドを構築することを考える。 このステップはソートのため、O(|Sj |log |Sj|)時間がかかる。 しかし、点を適切なソート順に格納すれば、このグリッドは O(|Sj|) = O(2j) 時間で構築できる。 (jは0から⌊log n⌋の間の任意の値を取ることができるので、挿入時間は大きく変動する。 しかし、第2段階の償却時間はO(log n)で束縛されると主張する。
この主張を証明するために、空集合Sから始めて、一連の挿入をn回行うものと仮定する。 これらの挿入の間に、大きさ2jの部分集合に対してグリッドを構築する回数をkjとすると、kjは最大で1＋⌊log n⌋ビットからなる整数の数で、j番目の下位ビットが1になり、（j＋1）番目のビットが0になる数に等しくなる。 すなわち、
n回の挿入の間に第2ステップに費やされる総時間は
により制限されるので、この主張を証明することになる。
最も近いペアを維持するためのアルゴリズム全体の実行時間は、O(log 2n)最悪ケース時間＋挿入ごとの償却時間O(log n)で制限されることを示しました。 標準的な技術（Overmars参照）を用いれば、第二段階が最悪の場合対数時間を要するようにデータ構造を変換することができる。 したがって、我々は、挿入ごとにO(log 2n)最悪の場合の時間で最も近いペアを維持するデータ構造を有する。 この構造体はサイズO(n)である。
アルゴリズムの第1段階はO(log 2n)時間かかるが、第2段階はO(log n)時間だけかかることに注意されたい。 これは、改良が可能であることを示唆している。 実際、nを2進数で書く代わりに、log nを底とする数体系を使う。 (Overmars または Schwarz を参照) この方法では、両方のステップで O(log 2n/log log n) の時間がかかるが、使用するスペースは線形である。
したがって、挿入ごとに最悪の場合 O(log2 n /log log n) 時間で最も近いペアを維持する線形サイズのデータ構造がある。 このアルゴリズムは、新しい点pを含むグリッドセルを見つけるためにフロア関数を使用することに注意。グリッドを劣化グリッドで置き換えることにより、アルゴリズムは代数計算木モデルで実装することができる。 二進法におけるnの表現に基づくデータ構造を再び考えてみる。 主な観察結果は次の通りである。 点pを挿入すると、ai = 1のような各iについて、pを含むδi -girdのセル（と隣接するセル）を見つける。 Schwarz and Smidにおいて、分数カスケード法は、これらの問い合わせをすべて合わせてO(log n log n)時間で解くことができるように拡張できることが示されている。 主な問題は、異なるグリッドサイズを持つグリッドを持つことです。 したがって、これらすべてのサイズと「互換性のある」グリッドセル上の順序を導入する必要があります。 このような順序が定義されている。 その結果、すべてのグリッドで点pを見つけるには、O(log n)回の比較が必要となる。 しかし、この順序は非常に複雑であるため、各比較は O(log log n)の時間を要する。 全体として、我々は、挿入ごとにO(log n log log n)の償却時間で最も近いペアを維持するサイズO(n)のデータ構造を得ることができる。 この結果を得るためには、floor関数が必要であることに注意。 これはおそらくワーストケースで作ることができるが、詳細は面倒であろう。
最後に、上記のデータ構造の拡張について言及する。 上記のような構造は、点だけを挿入することを多用している。 しかし、この構造はDobkinとSuriによって定義された半オンライン更新を扱うために適応できることが判明した。 一連の更新は、挿入がオンラインである場合、つまり、順序が不明である場合、セミオンラインと呼ばれるが、点が挿入されるとき、それが挿入された瞬間から何回目の更新で削除されるかが分かるようになっている。 この削除に関する特別な情報は、点が削除されるとき、それが常に小さなサブセットを格納するグリッドに含まれることを保証するために使用することができる。 また、削除の際に最小距離が増加する可能性があるため、最も近いペアを効率的に更新するための情報をデータ構造内に追加している。 このようにして、最も近いペアを保持するデータ構造をサイズO(n)で実現し、半オンライン更新あたりの最悪時間O(log 2n)を実現する。 詳しくは、Dobkin and Suri and Smid .
を参照されたい。