Finding the distance between the two closest points in a 2-D plane

Question

Here is my code:

import sys
import math
def dist(a,b):
    return math.hypot((b[0]-a[0]),(b[1]-a[1]))

def minimum_distance(x, y):
    points = list(zip(x,y))
    points_y = sorted(points, key= lambda z:z[1])
    points.sort(key=lambda g:g[0])
    return min_dist(points,points_y)

def min_dist(points,points_y):
    if len(points)==2: return dist(points[0],points[1])
    elif len(points)==3: return min(dist(points[0],points[1]),dist(points[0],points[2]),dist(points[1],points[2]))
    ave = (len(points)+1)//2
    yleft = [t for t in points_y if t[0]<=points[ave-1][0]]
    yright = [q for q in points_y if q[0]>=points[ave][0]]
    d1 = min_dist(points[0:ave],yleft)
    d2 = min_dist(points[ave:len(points)],yright)
    d = min(d1,d2)
    arr_split = [point for point in points_y if abs(point[0]- points[ave][0]) <= d]
    d_=2*(10**18)
    for i in range(len(arr_split)-1):
        for j in range(i+1,min(len(arr_split),i+7)):
            temp = dist(arr_split[i],arr_split[j])
            if temp<d_:d_=temp
    return min(d,d_)

Example input:([2,5,1],[3,6,2]) and output is \$ \sqrt 2 \$ since (2,3) and (1,2) are the closest points. The input arrays to minimum_distance are the x and y values of each point respectively and the inputs to min_dist are the points sorted based on their x values and y values respectively.

I have implemented pre-sort and have used computational geometric theory (comparison between 7 points only in the strip) to make the time complexity \$ O(n \log n) \$ and my code works swiftly and correctly for most test cases. However, for some hidden test cases generated by Coursera, my code is taking more than 20 seconds. Any optimisations/ corrections?

Answer 1

Coding style

Your code is difficult to read because it is written very condensed.

There is a well-established coding style for Python, the PEP8 coding style, and conformance to that style can be checked online at PEP8 online.

In your case it reports “missing space around operator” in almost every code line, also “line too long” and “multiple statements on one line” violations. As an example,

elif len(points)==3: return min(dist(points[0],points[1]),dist(points[0],points[2]),dist(points[1],points[2]))

is better written as

elif len(points) == 3:
    return min(dist(points[0], points[1]),
               dist(points[0], points[2]),
               dist(points[1], points[2]))

Variable naming

Another aspect which makes the code difficult to understand is the naming of variables. Here are some examples:

points_y = sorted(points, key= lambda z:z[1])
points.sort(key=lambda g:g[0])

The parameter names z and g seem to be arbitrary. Why are they different at all if they both refer to a point? Similarly at

yleft = [t for t in points_y if t[0]<=points[ave-1][0]]
yright = [q for q in points_y if q[0]>=points[ave][0]]

Why t and q? I'd suggest point or p in all those places.

def min_dist(points,points_y):

Both parameters contain all points, just sorted differently (by x and y, respectively). Why the asymmetry in the parameter names? I'd suggest

def min_dist(points_x, points_y):

here, plus a doc comment explaining the meaning of the parameters.

ave = (len(points)+1)//2

makes one think of “average” but is just half of the list length.

Some simplifications

import sys

is not needed. The inner parentheses in

return math.hypot((b[0]-a[0]),(b[1]-a[1]))

are not needed. The elif in

elif len(points)==3:

can be replaced by an if. The slicing in

d1 = min_dist(points[0:ave],yleft)
d2 = min_dist(points[ave:len(points)],yright)

can be simplified to

d1 = min_dist(points[:ave], yleft)
d2 = min_dist(points[ave:], yright)

Validate the input

The program aborts with RecursionError or IndexError if zero or one point are passed to the function. You should validate the input and throw an appropriate exception in those cases.

A possible problem

If points[ave-1][0] == points[ave][0] (which means that more than one point lies on the dividing vertical line) then elements from the point_y list are assigned to both yleft and yright:

yleft = [t for t in points_y if t[0]<=points[ave-1][0]]
yright = [q for q in points_y if q[0]>=points[ave][0]]

which means that in the recursive calls

d1 = min_dist(points[0:ave],yleft)
d2 = min_dist(points[ave:len(points)],yright)

the second list is not necessarily a rearrangement of the first list anymore.

I haven't found an example where this leads to a wrong result, but it could be an performance problem because “too large” lists are passed down the recursion. As an extremal case, if all points have the same x-coordinate then yleft and yright will always be the complete initial points_y list.

Performance improvements

points[ave][0]] is accessed multiple times, it might be advantageous to assign that value to a variable once.

The initial value

d_=2*(10**18)

is a bit arbitrary, but actually not needed: In the following loop we are only interested in points having a distance less than the previously computed minimum distance in the left and right half:

d = min(d1, d2)
# ...
for i in range(len(arr_split) - 1):
    for j in range(i+1, min(len(arr_split), i + 7)):
        temp = dist(arr_split[i], arr_split[j])
        if temp < d:
            d = temp
return d

And while it is true that pairs of points having a distance less than d are at most seven (or six?) indices apart, it seems to be more efficient to leave the inner loop if the y-coordinates differ by d or more:

for i in range(len(arr_split) - 1):
    for j in range(i + 1, len(arr_split)):
        if arr_split[j][1] - arr_split[i][1] >= d:
            break
        temp = dist(arr_split[i], arr_split[j])
        if temp < d:
            d = temp
return d

Further suggestions

Instead of storing the point coordinates a a tuple you could define a custom class

class Point:
    __slots__ = ('x', 'y')

    def __init__(self, x, y):
        self.x = x
        self.y = y

so that you can access the x- and y-coordinates of a point with p.x and p.y instead of subscripting.