Given a collection of points on a 2D plane, find the pair that is closest to each other

Full disclosure: I'm working on this for an online course. However, my goal is really just to get a pointer to where the issue is.

The goal is to implement the closest points problem, that is, given a set of points on a 2D plane, find the shortest distance between two points. After lots of stress-testing and debugging, I am confident the algorithm is correct. However, it is not fast enough, which is the problem I want to solve.

My algorithm is the implementation of what is described in that page, and includes the following optimisations:

• Sort the arrays before passing them to the function;

• Keep track of minimum distance so far and stop if it equals 0;

• When considering the strip in the middle, only calculate the distance between a point and the next one if the distance between their x-coordinates and the distance between their y-coordinates is smaller than the minimum distance found so far;

The main parts of the code are

double min_distance(const vector points_x, const vector points_y, double current_delta) {
  // Base case - sets of 3 points or fewer
  if (points_x.size()  x_left;
  vector x_right;
  vector y_left;
  vector y_right;

  // Creates the x_left and x_right arrays
  for (int i = 0; i  y_strip;
  // Creates the y_strip sorted by its y coordinate
  for (int i = 0; i = min_x && points_y[i].x <= max_x) {
      y_strip.push_back(points_y[i]);
    }
  }
  // Find the minimum distance in the strip
  double min_strip = mid_min_distance(y_strip, delta);
  return min(delta, min_strip);
}

for recursively calculating the smallest distance on the left and right sides, and

```
double mid_min_distance(const vector y_strip, double delta) {
// If mid_region is empty or contains just 1 point
if (y_strip.size() < 2) return delta;

double mid_min = minimal_distance(y_strip[0], y_strip[1]);
double mid_min_distance = mid_min;
// Brute force to inner points
for (int i = 0; i < y_strip.size(); i++) {
for (int j = i + 1; j < y_strip.size();

Comments out of sync with code

// Recursively solve left
  double min_left = min_distance(x_left, y_left, current_delta);
  if (min_left == 0) return min_left;

  // Recursively solve left
  double min_right = min_distance(x_right, y_right, current_delta);
  if (min_right == 0) return min_right;

Pretty sure the second comment should be "recursively solve right"--or omitted entirely, since it's pretty easily deduced from the code.

Parameter passing

Right now, you're passing a couple of std::vector parameters by value. You almost certainly want to pass by reference instead. I'd also at least consider passing either iterators or (perhaps) something range-like, such as a pair of iterators signifying a range in a collection.

Using this, creating the left and right "arrays" might look something like this:

range x_left{0, x_mid};
range x_right{x_mid, x_end};

range y_left{0, y_mid};
range y_right{mid, y_end};

The big difference here is that we're just keeping track of positions in the original vectors, rather than copying the entire contents of each original vector every time we make a recursive call (which is compounded when you pass by value, so you end up making not just one, but two copies of each sub-array to do your recursive call).

[[probably more to follow]]

StackExchange Code Review Q#158345, answer score: 5