## Class FarthestPair

• Object
• edu.princeton.cs.algs4.FarthestPair

• public class FarthestPair
extends Object
The FarthestPair data type computes the farthest pair of points in a set of n points in the plane and provides accessor methods for getting the farthest pair of points and the distance between them. The distance between two points is their Euclidean distance.

This implementation computes the convex hull of the set of points and uses the rotating calipers method to find all antipodal point pairs and the farthest pair. It runs in O(n log n) time in the worst case and uses O(N) extra space. See also ClosestPair and GrahamScan.

For additional documentation, see Section 9.9 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:
Robert Sedgewick, Kevin Wayne
• ### Constructor Summary

Constructors
Constructor Description
FarthestPair​(Point2D[] points)
Computes the farthest pair of points in the specified array of points.
• ### Method Summary

All Methods
Modifier and Type Method Description
double distance()
Returns the Euclidean distance between the farthest pair of points.
Point2D either()
Returns one of the points in the farthest pair of points.
static void main​(String[] args)
Unit tests the FarthestPair data type.
Point2D other()
Returns the other point in the farthest pair of points.
• ### Constructor Detail

• #### FarthestPair

public FarthestPair​(Point2D[] points)
Computes the farthest pair of points in the specified array of points.
Parameters:
points - the array of points
Throws:
IllegalArgumentException - if points is null or if any entry in points[] is null
• ### Method Detail

• #### either

public Point2D either()
Returns one of the points in the farthest pair of points.
Returns:
one of the two points in the farthest pair of points; null if no such point (because there are fewer than 2 points)
• #### other

public Point2D other()
Returns the other point in the farthest pair of points.
Returns:
the other point in the farthest pair of points null if no such point (because there are fewer than 2 points)
• #### distance

public double distance()
Returns the Euclidean distance between the farthest pair of points. This quantity is also known as the diameter of the set of points.
Returns:
the Euclidean distance between the farthest pair of points Double.POSITIVE_INFINITY if no such pair of points exist (because there are fewer than 2 points)
• #### main

public static void main​(String[] args)
Unit tests the FarthestPair data type. Reads in an integer n and n points (specified by their x- and y-coordinates) from standard input; computes a farthest pair of points; and prints the pair to standard output.
Parameters:
args - the command-line arguments