aha, finally a chance to post my only meaningful contribution to computer science:

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=tru...

draft here (because I can't give away the final version): https://github.com/BrendanBenshoof/pyVHASH/raw/master/Paper/...

Nifty because it is distributed, works in any metric space where voronoi regions make sense (XOR and non-euclidian ones as a start!) and easy to make into an online algorithim that updates as nodes join and exit.

basically:

   given a center point $center$
   given a list of candidate points $candidate$
   to output a list $peers$
   
   sort $candidates$ by distance from $center$
   remove the closest candidate and add to $peers$ (it will always be a delaunay peer)
   for $c$ in candidates:
      if any member of $peers$ is closer to $c$ than $center$ then reject $c$
      else add $c$ to $peers$

essentially this generates most of a delaunay triangulation, and you can quickly find the voronoi generator of a given point by greedily traversing the resulting graph.