Air Traffic Coordination Algorithm

The closest pair of points problem is a computational geometry problem. Given n points in a metric (2D space), find a pair of points with the minimum distance between them. The first thing that comes to mind when thinking about air traffic control is preventing possible collisions, so some prevention strategy must exist. The simplest one to avoid collisions is to have an algorithm that can detect if two planes have come too close to each other. We will notify the pilots of the possible jeopardy.

The algorithm will be applied to a two-dimensional surface with a pair of points (planes) and observed to determine which points have the closest distance. The closest pair problem for points in the Euclidean plane was among the first geometric problems treated at the origins of the systematic study of the computational complexity of geometric algorithms. This article aims to provide the institution behind the implementation of the closest pair of points algorithm.

Problem Statement

Given a set of points {P1, P2, P3, . . . . . ., Pn} in a two-dimensional plane, find the pair of points {Pi, Pj} that are closest together.

Goal

Our goal as described above is to find the pair of points {Pi, Pj} that are closest together.

• We can find that with brute-force which will give an O(n2) time complexity due to checking every pair of points.
• We can do it faster with divide and conquer approach with O(n log n) time complexity.

How to find the distance between two points?

The Euclidean distance between two points in Euclidean space is the length of the line segment between them. It can be calculated from the cartesian coordinates of the points using the Pythagorean theorem and is therefore called the Pythagorean distance.

Let's assume we have three points A, B and C in the coordinate axis, Let's see the formula for finding the distance between A and B.

Euclidean Distance Formula: AB= √((B.x-A.x)² + (B.y — A.y)²)

Algorithm Implementation

Brute Force

As we can see in the below image there are only 4 points. we can solve this problem by running a brute force, that will compute the distance between each point iteratively. The solution will be reduced to choosing 2 points out of N. As the N value is 4 we will end up having time complexity O(16) which is constant time. Solving this problem for a small number of points with brute force is fine but if there are hundreds or thousands of points, solving with brute force will not help.

We can solve this problem for a large number of points with divide-and-conquer and small data (potentially size less than or equal to 3) we can use brute force.

Closest Pair of Points Algorithm: Strategy and Explanation

The Closest Pair of Points algorithm is a fundamental problem in computational geometry, where we aim to find the two closest points in a given set. The divide-and-conquer approach significantly improves efficiency compared to the brute-force method, reducing the time complexity to O(n log n). Below is a step-by-step explanation of the strategy used in the provided Java implementation.

Create Point class

Let's set up our Point class first with a utility method for calculating Euclidean distance. The Euclidean distance formula is used to determine the distance between two points:

d(p1, p2) = √((p1.x-p2.x)² + (p1.y — p2.y)²)

This formula is implemented in the distance method of the Point class:

class Point {
    public int x;
    public int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
   
   // Euclidean distance
    public static double getDistance(
            Point p1,
            Point p2
    ) {
        return Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
    }
}        

Recursive Division of Points

The closeUntil method follows the Divide and Conquer approach. It works by splitting the set of points into two halves:

• Otherwise, we recursively compute the closest pair of points in both the left and right halves of the dataset.

private double closeUntil(Point[] points, int start, int end) {
    if (end - start <= 3) {
        return bruteForce(points, end);
    }

    int mid = start + (end - start) / 2;
    Point midPoint = points[mid];

    double distanceLeft = closeUntil(points, start, mid);
    double distanceRight = closeUntil(points, mid, end);
    double minDistance = Math.min(distanceLeft, distanceRight);
    
    return Math.min(minDistance, minDistanceInStrip(points, midPoint, minDistance, end));
}        

This step ensures that we progressively reduce the problem size and solve it recursively.

Finding the Closest Pair in the "Strip"

After calculating the closest pairs in the left and right halves, we check if there is a closer pair that crosses the dividing line (midpoint).

• We collect points that lie within minDistance from the midpoint into a strip.

• We sort the strip points based on their Y-coordinates (as the closest pair is likely to be vertically aligned).

• We compare only nearby points within the strip, ensuring efficient computation.

private double minDistanceInStrip(Point[] points, Point midPoint, double minDistance, int end) {
    var stripPoints = new Point[end];
    int k = 0;
    for (int i = 0; i < end; i++) {
        if (Math.abs(points[i].x - midPoint.x) < minDistance) {
            stripPoints[k++] = points[i];
        }
    }

    Arrays.sort(stripPoints, 0, k, new PointYComparator());

    for(int i = 0; i < k; i++) {
        for(int j = i + 1;
            j < k && (stripPoints[j].y - stripPoints[i].y) < minDistance && distance(stripPoints[i], stripPoints[j]) < minDistance;
            j++
        ) {
            minDistance = distance(stripPoints[i], stripPoints[j]);
        }
    }

    return minDistance;
}        

This step optimizes the closest pair search by reducing unnecessary comparisons and leveraging the sorted order.

Brute Force Approach for Small Sets

If the number of points is 3 or fewer, we calculate the pairwise distances directly using a brute-force method. This ensures accuracy for small cases before applying recursion for larger cases.

private double bruteForce(Point[] points, int end) {
    double min = Double.MAX_VALUE;
    for(int i = 0; i < end; i++) {
        for (int j = i + 1; j < end; j++) {
            min = Math.min(min, distance(points[i], points[j]));
        }
    }
    return min;
}        

Sorting Points by X and Y Coordinates

Since sorting is an essential step, we define comparators to sort points based on X and Y coordinates.

Sorting by X-coordinate:

class PointXComparator implements Comparator<Point> {
    @Override
    public int compare(Point o1, Point o2) {
        return Integer.compare(o1.x, o2.x);
    }
}        

Sorting by Y-coordinate (used in the strip region):

class PointYComparator implements Comparator<Point> {
    @Override
    public int compare(Point o1, Point o2) {
        return Integer.compare(o1.y, o2.y);
    }
}        

Final Output

Once the algorithm executes, it prints the minimum distance between the closest pair of points.

DecimalFormat df = new DecimalFormat("#.######");
System.out.println("The smallest distance is " +
        df.format(closest.close(P)));        

For the given example points, the output would be:

The smallest distance is 1.414214        

This result corresponds to the closest pair of points in the dataset.

Conclusion

The Closest Pair of Points problem demonstrates the power of the Divide and Conquer paradigm in reducing time complexity from O(n²) (brute-force) to O(n log n). By leveraging sorting, recursive division, and efficient strip handling, we can solve the problem in an optimized manner, making it highly suitable for large-scale geometric computations.

The complete algorithm can be found on GitHub.