Possible Duplicates:
which data structure is appropriate to query “all points within distance d from point p”
Storing objects for locating by x,y coordinates
I have a list of items, each with a location in 2D space (specified using euclidean geometry, i.e. as an (x, y) coordinate pair).
How should I store this list (e.g. hashtable? etc...) to allow myself to be able to efficiently look up all items in that list that are within a distance D of some point (x, y)?
(Again, I'm talking about simple straight line distance i.e. d ^ 2 = dx ^ 2 + dy ^ 2)
