Small World

Given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance.

For example, given a set of points where each line is of the form: ID x-coordinate y-coordinate

1  0.0      0.0
2  10.1     -10.1
3  -12.2    12.2
4  38.3     38.3
5  79.99    179.99

Your program should output:

1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1

This is facebook's smallword puzzle, but I am only asking for a O(n²) solution.



Below is a program that will solve the smallworld puzzle in n-squared time. Notice that this will not be accepted by the facebook robot as it is too slow so don't even bother submitting it (I already tried). If you don't believe me try running it with 10,000 input coordinates.

There is a way to do this in close to linear time, can you figure out how?

#!/usr/bin/env python
import sys
from math import sqrt

class Node:
    def __init__(self,name,x,y):
        self.name =  name
        self.x = x
        self.y = y
        e = Edge(self,self)
        e.distance = 1e1000
        #3 smallest edges, sorted by distance
        self.closest = [e,e,e]

    def __str__(self):
        return str(self.name) + " " + self.closest[0].b.name + "," + self.closest[1].b.name + "," + self.closest[2].b.name

    #O(1) since we keep self.closest limited to 3
    def addNeighbor(self,other):
        """Add other to the closest list, but only if it is
           closer than the farthest one in the list."""
        e = Edge(self,other) # I am always first
        if (e.distance < self.closest[2].distance):
            self.closest.append(e)
            self.closest.sort()
            self.closest = self.closest[:3]
        if (e.distance < other.closest[2].distance):
            e = Edge(other,self) # I am always first
            other.closest.append(e)
            other.closest.sort()
            other.closest = other.closest[:3]


class Edge:
    def __init__(self, a, b):
        self.a = a
        self.b = b
        dx = (a.x - b.x)
        dy = (a.y - b.y)
        self.distance = sqrt(dx*dx + dy*dy)

    def __cmp__(self,other):
        return cmp(self.distance, other.distance)

    def __str__(self):
        return self.a.name + "-" + self.b.name

filename = sys.argv[1]
f=open(filename)
nodes = []

# O(n), where n is the number of nodes (friends)
for l in f:
    items = l.split()
    n = Node(items[0], float(items[1]), float(items[2]))
    nodes.append(n)

# O(n^2)
for i in xrange(0,len(nodes)-1):
    for j in xrange(i+1,len(nodes)):
        nodes[i].addNeighbor(nodes[j])

# O(n)
for n in nodes:
    print n