edu.princeton.cs.algs4

Class ClosestPair

java.lang.Object

edu.princeton.cs.algs4.ClosestPair

public class ClosestPair
extends java.lang.Object

The ClosestPair data type computes a closest pair of points in a set of n points in the plane and provides accessor methods for getting the closest pair of points and the distance between them. The distance between two points is their Euclidean distance.

This implementation uses a divide-and-conquer algorithm. It runs in O(n log n) time in the worst case and uses O(n) extra space.

See also FarthestPair.

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

Constructor Summary

Constructors

Constructor and Description
ClosestPair(Point2D[] points) Computes the closest pair of points in the specified array of points.

Method Summary

Modifier and Type	Method and Description
double	distance() Returns the Eucliden distance between the closest pair of points.
Point2D	either() Returns one of the points in the closest pair of points.
static void	main(java.lang.String[] args) Unit tests the ClosestPair data type.
Point2D	other() Returns the other point in the closest pair of points.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ClosestPair

public ClosestPair(Point2D[] points)

Computes the closest pair of points in the specified array of points.

Parameters:

points - the array of points

Throws:

java.lang.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 closest pair of points.

Returns:

one of the two points in the closest 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 closest pair of points.

Returns:

the other point in the closest pair of points null if no such point (because there are fewer than 2 points)

distance

public double distance()

Returns the Eucliden distance between the closest pair of points.

Returns:

the Euclidean distance between the closest 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(java.lang.String[] args)

Unit tests the ClosestPair data type. Reads in an integer n and n points (specified by their x- and y-coordinates) from standard input; computes a closest pair of points; and prints the pair to standard output.

Parameters:

args - the command-line arguments