Closest pairs by vertical ascent

Question

The standard sweep line algorithm for nearby pairs is well known, as described here , which uses a sweep line to horizontally sweep across multiple points, supporting only those that are at the current best distance from the current point.

Usually, the points must first be sorted by the x coordinate, and the bounding box (std :: set in the case of the C ++ implementation) should be sorted by the y coordinate, as can be seen from this C ++ implementation .

However, when I tried to implement it, I accidentally forgot to sort the points by the x coordinate and instead sorted them by the y-coordinate. Surprisingly, it still seemed to work. You can see my implementation here , which basically follows a slightly modified version of the standard algorithm for the closest pairs of lines:

#include <iostream>
#include <set>
#include <algorithm>
#include <math.h>
#include <vector>

using namespace std;

#define x second
#define y first

typedef pair<long long, long long> pll;

inline double dist(pll p1, pll p2)
{
    return sqrt((double) (p2.y - p1.y)*(p2.y - p1.y) + (p2.x - p1.x)*(p2.x - p1.x));
}


int main(int argc, const char * argv[])
{
    int numPoints;
    cin >> numPoints;

    vector <pll> points;
    points.resize(numPoints);

    for (int i = 0; i < numPoints; i++)
    {
        cin >> points[i].x >> points[i].y;
    }

    //Sorts the points by y coordinate (because y is first)
    sort(points.begin(), points.end());

    double shortestDistSoFar = INFINITY;
    set <pll> boundingBox; //Bounding box maintained by y-coordinate
    boundingBox.insert(points[0]);

    int left = 0;

    pll best1, best2;

    for (int i = 1; i < numPoints; i++)
    {
        //Maintain only points to the left of the current point whose distance is less than bestDist
        while ((left < i) && (points[i].x - points[left].x > shortestDistSoFar))
        {
            boundingBox.erase(points[left]);
            left++;
        }

        //Consider only points within bestDist of the current point
        for (auto it = boundingBox.lower_bound(pll(points[i].y - shortestDistSoFar, points[i].x - shortestDistSoFar));
             it != boundingBox.end() && it->y <= points[i].y + shortestDistSoFar; it++)
        {
            if (dist(*it, points[i]) < shortestDistSoFar)
            {
                shortestDistSoFar = dist(*it, points[i]);
                best1 = *it;
                best2 = points[i];
            }
        }

        boundingBox.insert(points[i]);
    }

    return 0;
}

Visit each point in ascending y-coordinate and for each point check all points from y-bestDist to y + bestDist, updating bestDist when a new shortest distance is found and remove points from the set whose coordinate distance from the current point is greater than bestDist .

This modified algorithm still works (I tested only a few cases), and the running time is still O (N lgN)?

Answer 1

( , ). O(n ^ 2), , .

( python3):

from sys import argv

n = int(argv[1])
dy = 1
dx = -n
print(n)
for i in range(n):
  print(dx * i, dy * i)

, O(n ^ 2) n.

: ( y) x-, . , y x, . ( n * (n - 1) / 2).

, :
-, g++ -std=c++11 -O2 closest_pair.cpp. :

temp$ python3 gen.py 10000 > input
temp$ time ./a.out < input

real    0m0.805s
user    0m0.797s
sys     0m0.008s

temp$ python3 gen.py 30000 > input
temp$ time ./a.out < input

real    0m7.195s
user    0m7.198s
sys     0m0.004s

temp$ python3 gen.py 50000 > input
temp$ time ./a.out < input

real    0m23.711s
user    0m23.725s
sys     0m0.004s

, .