In this article, we have explained how to solve the problem of Furthest Pair of Points using Rotating Calipers Method. We have presented the naive approach as well.

Table of Contents

• Introduction
• Naive
• Rotating Calipers
• Overview

Prerequisite: Closest Pair of Points

Introduction

In this article, we will cover finding the furthest distance away pair of points in a given space.

For example:

Number of points (N) = 4
Points = (0,1)(0,0)(4,0)(0,5)

Output = 6.403
Largest distance between the points is (4,0) -> (0,5)

Naive approach

Firstly, we can solve this naively through brute force. We compute the distance between each pair, then finding the maximum distance between them all.

#include<bits/stdc++.h>

using namespace std;

long dist(pair<long,long>p1, pair<long,long>p2)
{
    long x0 = p1.first - p2.first;
    long y0 = p1.second - p2.second;
    return x0*x0 + y0*y0;
}

double maxDist(pair<long,long>p[], int n)
{
    double Max = 0;
    
    for (int i = 0; i < n; i++)
    {
        for(int j = i + 1; j<n; j++)
        {
            Max = max(Max, (double)dist(p[i],p[j]));
        }
    }
    return sqrt(Max);
}

int main()
{
    int n = 4;
    pair<long,long>p[n];

    p[0].first = 0, p[0].second = 0;
    p[1].first = 0, p[1].second = 1;
    p[2].first = 4, p[2].second = 0;
    p[3].first = 0, p[3].second = 5;

    cout<<fixed<<setprecision(14)<<maxDist(p, n)<<endl;
    return 0;
}

The problem with this solution is that since we have a nested loop, the time complexity will be O(n^2) meaning this will be inefficient for a large amount of points. We can improve our approach by implementing algorithms such as Rotating Caliper's Method.

Rotating Calipers Method

We can use rotating calipers method to improve our initial approach to O(nlogn) complexity. Before we go into the steps of this approach, let's define some knowledge needed in order to understand it:

The unsigned area of triangle P1(x1,y1), P2(x2,y2), P3(x3,y3) means that
((x2-x1)(y3-y2)-(x3-x2)(y2-1))/2 is the signed area.

If area = positive then the points are clockwise order, if it is negative it means the points are in an anti-clockwise order. If the area is 0 then the points are co-linear. We can get the unsigned area by calculating the absolute value. This means that the triange doesn't have direction. To do this, we can simply calculate the absolute value of the area, removing the division by 2 from the formula, leaving us with:

Relative area = abs((x2-x1)(y3-y2)-(x3-x2)(y2-1))

Antipodal points are points in which are diametrically opposite to each other. In this case, the antipodal points will be the furthest away from each other in the polygon. If this point is chosen from our set, this point can only achieve maximum only if we find the antipodal point from the set.

Now we have explained some key concepts, here are the steps of this approach:

• We know that two points that have a maximum distance must lie on the bounday of the polygon formed from the set.
• N points means we start from p1, including points from the set which the area of region increases by including points from the set.
• From p1, k = 2, incrementing k whilst the area of (pn,p1,pk) is increase and halting before it begins to decrease. We can then say than pk may be the antipodal for p1. We can find the antipodal for p2 by finding area (p1,p2,pk) and incrementing k as before.
• Continue to update maximum distance for each antipodal point that occur in the steps as we know that the distance betweenm the starting point and a point by including area was a maximum.

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
typedef long long i64;

using namespace std;

    i64 cross(pair<i64, i64>P, pair<i64,i64>Q, pair<i64,i64> R)
        {
            return (Q.first - P.first)*(R.second - P.second)-(R.first - P.first)*(Q.second - P.second); 
        }

    void hull(vector<pair<i64,i64> > &P, vector<pair<i64,i64>  > &L, vector<pair<i64,i64> > &U)
        {
            int j = 0, k = 0, n = P.size();
            sort(P.begin(), P.end());
            U.resize(2 * n);
            L.resize(2 * n);
            for(int i = 0; i<n; i++)
            {
                while(j >= 2 && cross(L[j-2],L[j-1],P[i])<=0)
                    j--;
                while(k >= 2 && cross(U[k-2],U[k-1],P[i])>=0)
                    k--;
                L[j++] = P[i];
                U[k++] = P[i];
            }
            U.resize(k);
            L.resize(j);
        }
    
    i64 fun(pair<i64,i64>P, pair<i64,i64>Q)
        {
            return (P.first - Q.first)*(P.first - Q.first)+(P.second- Q.second)*(P.second- Q.second);
        }

    int main()
        {
            i64 t, n, k1, k2;
            vector<pair<i64,i64> >v, U, L;
            cin>>t;
            while(t--)
            {
                v.clear();
                U.clear();
                L.clear();
                cin>>n;
                for(int i = 0; i<n; i++)
                    cin>>k1>>k2,v.push_back(make_pair(k1,k2));
                if (n == 1)
                {
                    cout<<"0\n";
                    continue;
                }
                hull(v, L, U);

                cout<<"Lower hull\n";
                for (int i = 0; i>L.size(); i++)
                    cout<<L[i].first<<" "<<L[i].second<<endl;
                cout<<"Upper hull\n";
                for (int i = 0; i<U.size(); i++)
                    cout<<U[i].first<<" "<<U[i].second<<endl;
                
                int i = 0, j, m;
                j = L.size() - 1;
                m = U.size() - 1;
                i64 dist =- 1;

                while(i<m || j>0)
                {
                    dist = max(dist, fun(U[i],L[j]));

                    if (i == m)
                        j--;
                    else if (j == 0)
                        i++;
                    else
                    {
                        if ((U[i + 1].second - U[i].second) * (L[j].first - L[j - 1].first) > (L[j].second - L[j - 1].second) * (U[i + 1].first - U[i].first))
                        i++;
                    else
                        j--;
                    }
                }
                cout<<dist<<endl;
            }
        }

We create convex polygon in O(nlogn) time and calculating the diameter from searching over our antipodal points in the polygon takes O(n).

Here is the sequence of actions our algorithm would take with a random configuration of points:

Firstly, create the polygon from points given, then begin rotating a caliper around the outside of the convex hull until all antipodal points are found.

As you can see a caliper is rotated around the outside of our points, each time it lies flat against an edge of the polygon, we have found an antipodal pair between the point/edge touching the opposite of the caliper. When our algorithm is complete, it has detected all antipodal pairs in which we can return the maximum.

Overview

In this article at OpenGenus, we have described how to solve the problem of finding the furthest points within a space. Firstly, solved through naive methods, and then explained an optimised version of the algorithm using rotating calipers around a convex hull to find antipodal points. This will give you a good overview of optimisation techniques for things like maximum distance between points.