# Optimize QuadTree to find K Nearest Neighbors

I'm looking a way to make my k nearest neighbors search more efficient. The context of the question is that I'm given a list of topics that have a unique ID (integer) and a (x,y) coordinate (floats) associated with each topic. Subsequently, I'm given another point and the number of nearest topics to find around the given point. The topics need to be returned in order of distance to the point. However, if the distance between two topics is <= .001, the topic with the larger ID should come first. Here's the full description if you're looking for a better description: http://www.quora.com/challenges#nearby.

My solution is implemented using a QuadTree. I'm looking for ways to make the search function of the QuadTree faster.

In addition to the four quadrants (children QuadTrees), the QuadTree class has two member variables x and y representing the point at which it is split into northeast, northwest, southeast, and southwest. Both findTopics() and findTopicsWithinRadius() are functions of the QuadTree.

class Topic:
def __init__(self, x, y, val):
self.id = val
self.x = x
self.y = y

# point: (x,y) tuple
# numResponses: integer
def findTopics(self, point, numResponses):
topicToDistance = {}
update = topicToDistance.update
while len(topicToDistance) < numResponses:
# dont want to see topics in previous searches
def firstGreaterCmp(a, b):
if abs(a[1]-b[1]) <= .001:
if a[0].id < b[0].id:
return 1
if a[1] > b[1]:
return 1
return -1
topics = sorted(topicToDistance.items(), cmp=firstGreaterCmp)
# sorting by key may be faster than using a cmp function
topics = [x[0].id for x in topics]

# search for topics around the given point with distance in the range of [minimum, radius]
# minimum is used so topics are not considered more than once
# point: (x,y) tuple
# minimum: int
topics = {}
if not self.northwest:
# this is a leaf
for topic in self.topics:
dist = distance((topic.x, topic.y), point)
if minimum <= dist <= radius:
topics[topic] = dist