Two quick notes: First, the point is to not have to load the entire structure into RAM so the Voroni diagram would have to be coded into the database such that you could use a database index to find the part of the diagram that you need to worry about. I don't see a way to do that.

Second, the problem isn't that I'd have to compare a few more points, it is that I'd have to read records. The I/O for reading a record usually takes much longer than comparing a few hundred points would. So, yes, I did some extra work to avoid reading more records, but I don't think the resulting implementation was much more complicated than you'd get implementing the algorithm you described if you factor the problem well and deal with all of the edge/corner cases.

        - tye (but my friends call me "Tye")