Quaternary Tree

# "Spatial Tessellations: Concepts and Applications of Voronoi Diagrams," 2nd Ed.
# A. Okabe, B. Boots, K, Sugihara, S.N. Chiu, Wiley 2000
# p.245 Algorithm 4.3.1, Ch4 Algorithms for Computing Voronoi Diagram

# Given randomly generated 2D points pi (i=0..n) in the unit square 
# Find the closest generator pi to a point p

# construction: define mapping g: qtree -> generators (k = ceil(log(n)/log(4)))
# [1] assign a root bucket u0 to p0: g(u0) = [p0]
# [2] append pj to list of points that fall in a k-level bucket u: g(u) << pj
# [3] assign unassigned parent nodes u' of u to pj: g(u') = [pj]

# application [1]: distributed navigation
# visit in breadth-first search order and output g(u) iff g(u)!=g(u'), u': parent

# application [2]: the nearest neighbor at level l <= k
# find a nearest node u of any given point p, then g(u) is the nearest at level l.

Graphics modules not shown below (see "Maximum Distance Bisectors" as of 2007-02-25)

require 'geom'

# 2D point in the normalized [] square S[0..1, 0..1]
class QPoint < Point
  attr_accessor :nx, :ny

  def initialize nx, ny, *args
    @nx, @ny = nx, ny
    super((ScrHgt*@nx).to_i, (ScrHgt*@ny).to_i, *args)
  end

  def index level
    i = 2**level
    [(@nx*i).to_i, (@ny*i).to_i]
  end

end

# quaternary tree
class QTree
  attr_accessor :lvl, :idx, :hsh

  def initialize n
    @lvl = n
    @idx = Array.new n
    (0..n).each {|i| @idx[i] = (4**i - 1)/3}
    @hsh = Hash.new
  end
  
  def index level, i, j
    return 0 if level == 0
    @idx[level] + i + j*2**level
  end
  
  def add level, pnt
    i, j = pnt.index level
    key = index level, i, j
    ary = @hsh[key]
    if ary
      @hsh[key] = ary << pnt
    else
      @hsh[key] = [pnt]
    end
    until level == 0
      level = level - 1
      i = i/2
      j = j/2
      key = index level, i, j
      break if @hsh[key]
      @hsh[key] = [pnt]
    end
  end
   
  def out
    k = 0
    (0..@lvl).each {|l| n = 2**l
      (0...n).each {|i|
      (0...n).each {|j|
        ary = @hsh[index(l, i, j)]
        next unless ary
        mom = @hsh[index(l-1, i/2, j/2)][0] if l>0
        (0..ary.size).each {|m|
          pnt = ary[m]
          next if (!pnt or (l>0 && mom == pnt))
          p pnt
          k = k + 1
        }
      }
      }
    }
  end
  
end

if __FILE__ == $0
N = 3
qt = QTree.new N
(4**N).times {
  p = QPoint.new(rand, rand)
  qt.add(N, p)
}
qt.out
end

I have a little doubt on the claim of "uniformly distributed", since we see the points are arranged rather into slab patterns.