Package edu.princeton.cs.algs4

Class 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 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