Basically, these are hierarchical data structures (related to the binary

search tree). In the case of 2 dimensions: the quad tree uses 4 pointers

for each node, indicating the next node in the tree to check in each of the

4 quadrants; and the k-d tree uses one pointer per node. Creating these

structures boils down to sorting multidimensional data. There are many

papers and textbooks describing both of these, mostly tracing back to Jon

Bentley in the 1970's, and many textbooks have examples (see for instance,

H. Samet, "The Design and Analysis of Spatial Data Structures,"

Addison-Wesley, Reading, MA, 1990.). Perhaps the easiest introduction to

these is at the following links:

http://www.cs.umd.edu/~brabec/quadtree/index.html

http://shum.huji.ac.il/~bennun/muky/java/index.html

Check and compare the size and performance of the Rectangle Quadtree and the

PMR rectangle k-d tree demos for your situation. Somewhat more complicated

are the range tree and interval tree. I don't recall any code for these at

Graphic Gems or in O'Rourke's or Eberly's sites.

For other readers, regarding performance, please keep in mind the

limitations of the big-O notation. For example, O(n), does not give you a

time, but an approximate number of comparisons proportional to the time,

where the proportionality constant varies between languages and algorithms.

For simple methods,O(n), it takes less time t1 per comparison; for spatial

structures, O(log(n)), it takes a little more t2 per comparison, but there

is a big reduction in the number of comparisons ( i.e. t2*O(log(n)) is less

than t1*O(n) for n sufficiently large!). Thus, you will almost always

benefit if there is a sufficiently "large" number of items to compare.

>How would the algorithm look like if we are supposed to use a quad tree?

>I went by MS's original suggestion and it was indeed a strikingly (though

>it didn't strike me at first!) simple solution. It works but O(nquery x

log2(nexist))

>sounds interesting!

>Thx.

>CP Chandrasekar