Generates a set of points and uses rotating calipers and convex hull algorithms to find the pair of points with the farthest distance between each other.
Switch branches/tags
Nothing to show
Clone or download
Latest commit c91b0c6 Aug 7, 2015
Failed to load latest commit information.
.idea add picture Aug 7, 2015
out/production/FarthestPoint/com/company add picture Aug 7, 2015
src/com/company add picture Aug 7, 2015
FarthestPoint.iml initial commit Aug 7, 2015
LICENSE Initial commit Aug 7, 2015 Update Aug 7, 2015

Farthest Points in a Set

The goal is to identify the pair of points with the farthest distance between them. An obvious, yet inefficient approach to solve the problem is to scan every point and calculate its distance from every other point in the set. This would run with O(n^2) efficiency. A more efficient approach to the problem is to form a convex hull and analyze the hull with an algorithm to find the farthest two points. The convex hull is the set of points that form a polygon that contains all points in the set while forming only exterior reflex angles. The graphic below depicts the convex hull of a set of points, where the red dots are in the convex hull set and the white lines form the polygon:
alt tag
The convex hull is useful because the farthest two points are always in the convex hull set. This approach is more efficient in conjunction with rotating calipers because it takes less iterations to find the furthest pair than the brute force approach. This is because the gift wrapping method has O(nh) efficiency, where n is the number of points in the set and h is the number of points in the convex hull. Then, when searching for the furthest pair in the convex hull, the brute-force algorithm is O(h) instead of O(n). In addition, with rotating calipers, the convex hull approach is significantly more efficient.