Points Close Enough | Python Fiddle

import math
from random import randrange

first_line = True
points = {}
points_distance = 2.5
for i in range(100):
    points[(randrange(10), randrange(10))] = str(i)
# print num_points, points_distance
# print points

def group_points(seq):
    # base case: 2 points
    if len(seq) == 2:
        # if within distance, link the left point to the right point
        if (distance(seq[0], seq[1]) < dist):
            connect(seq[0], seq[1])
    # else divide by mid x and mid y
    else:
        index = len(seq)//2
        (midx, midy) = seq[index]
        lft, rgt = seq[index:], seq[:index]
        if len(lft) > 1: group_points(lft)
        if len(rgt) > 1: group_points(rgt)
        # on either side of the dividing line within distance, check all points in square
        connect_straddling_points(select_candidates(lft, midx), select_candidates(rgt, midx))
    
def connect_straddling_points(mid_points_lft, mid_points_rgt):
    for point_lft in mid_points_lft:
        for point_rgt in mid_points_rgt:
            if point_rgt[1] < (point_lft[1] - dist):
                continue
            else:
                # if they are within distance
                if (distance(point_lft, point_rgt) < dist):
                    connect(point_lft, point_rgt)
                elif point_rgt[1] > (point_lft[1] + dist):
                    break

def connect(p, q):
    connected[points[p]].append(points[q])
    connected[points[q]].append(points[p])

def select_candidates(seq, mid):
    mid_points = []
    for point in seq:
        if abs(point[0] - mid) < dist:
            mid_points.append(point)
    return mid_points

def distance(p, q):
    return math.hypot(p[0]-q[0], p[1]-q[1])

sequence = []
point_ids = []
connected = {}
for k, v in points.iteritems():
    sequence.append(k)
    point_ids.append(int(v))
    connected[v] = []
sequence.sort(key=lambda item: (item[0], item[1]))
dist = float(points_distance)
group_points(sequence)
# print connected
point_ids.sort()
for p in point_ids:
    print '%d %s' % (p, ' '.join(connected[str(p)]))

Python Fiddle

Python Cloud IDE