Algorithm to Compute the Shortest Distance between Points on Two Lines

Let U = [(xu0, yu0), (xu1, yu1), …, (xun, yun)] represent a increasing series of points; xu0 < xu1 && yu0 < yu1, etc.
Let D = [(xd0, yd0), (xd1, yd1), …, (xdn, ydn)] represent a decreasing series of points; xd0 < xd1 && yd0 > yd1, etc.

U and D are lists/vectors/arrays of a custom “Point” structure; define your “Point” structure.

Write a function that returns the distance between the one point in series U and the one point in series D that are closest to each other in 2D space.

Try to find a solution that minimizes the TIME complexity.

What is the time complexity of your solution? Use big-O notation.

Bruteforce with O(UD) complexity

The following C++ code implements a bruteforce algorithm that runs at O(UD) time complexity – check every pair of points between two lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

struct Point {
    double x;
    double y;
};
 
inline double sqr(double x) {
    return x * x;
}
 
double distance(const Point &p1, const Point &p2) {
    return sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
}
 
// O(UD) where U and D are lengths of the vector respectively.
double shortestDistance(const vector<Point> &U, const vector<Point> &D) {
    auto dis = DOUBLE_MAX;
    for (const auto &p1: U) {
        for (const auto &p2: D) {
            auto d = distance(p1, p2);
            dis = min(d, dis);
        }
    }
    return dis;
}

struct Point {
    double x;
    double y;
};

inline double sqr(double x) {
    return x * x;
}

double distance(const Point &p1, const Point &p2) {
    return sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
}

// O(UD) where U and D are lengths of the vector respectively.
double shortestDistance(const vector<Point> &U, const vector<Point> &D) {
    auto dis = DOUBLE_MAX;
    for (const auto &p1: U) {
        for (const auto &p2: D) {
            auto d = distance(p1, p2);
            dis = min(d, dis);
        }
    }
    return dis;
}

Do you have a better algorithm that run less time complexity? Let us know by commenting below.

–EOF (The Ultimate Computing & Technology Blog) —