Implement a \(\Theta(n \log n)\) divide-and-conquer algorithm for the following problem: Given is a collection of points in the plane. Find a pair of points with the smallest distance between them.

Assignment

Write a Python function distanceClosestPair which takes a filename as parameter and returns the square of the distance between a closest pair. The distance between two points is the Euclidean distance. Each line in the file contains two numbers representing the x- and y-coordinate of a point.

Example

In the example below we assume the file testdata_100_1.txt¹ to be located in the current directory.

>>> distanceClosestPair("testdata_100_1.txt")
65

Reference

• Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, “Introduction to Algorithms” (3rd edition), MIT Press, 2009 (par.33.4)