Closest & Farthest Pair of Points
A Java Swing app that finds the closest and farthest pair of points in a 2D cloud, pitting a brute-force strategy against a divide & conquer one both visually and in a benchmark that estimates where divide & conquer starts to pay off.
The problem
Project 3 of 7 for the Advanced Algorithms course at the Universitat de les Illes Balears — the one on divide & conquer.
Given a cloud of points, the closest pair can be found two ways: the naive O(n²) double loop over every pair, or the classic O(n · log n) divide & conquer that splits the plane, solves each half recursively and only re-checks the points inside the boundary strip. The farthest pair is bounded by the convex hull — the two most distant points are always hull vertices — so it is attacked with an O(n²) baseline and a hull-based method.
The application generates the cloud from a range of statistical distributions, draws it, highlights the winning pairs, and — in a separate benchmark workflow — plots how the running times of the strategies diverge as n grows, estimating the crossover point where divide & conquer starts to pay off.
How it works
- Two workflows, one shared view — an analysis tab (interactive point cloud with the closest / farthest pairs highlighted) and a benchmark tab (time-vs-size comparison chart); the side control and telemetry panels follow the active tab.
- Closest-pair strategies — brute force and divide & conquer, supported by spatial structures (a k-d tree, bucket / grid / strip cells) that keep the recursion and the strip check efficient.
- Farthest-pair strategies — a brute-force baseline and a convex-hull method, exploiting that the diameter of a point set lies on its hull.
- Point distributions — a whole family of generators (uniform, Gaussian, double-Gaussian, exponential, banded, collinear, lattice, sphere-shell, duplicate clusters) behind a common interface, to stress the algorithms on very different inputs.
- Crossover estimation — a Bolzano-based estimator locates the input size at which the two cost curves cross.
- MVC +
Notify/Reporter— from this project on, a dedicatedReportermediates all cross-package messages; the controller owns generation, execution and benchmarking, and the view only renders snapshots.
Running it
Requires a JDK 17 or newer — plain Java with Swing, no external dependencies or build tool. Open the P3/ folder in IntelliJ IDEA and run practice3.Main. In the analysis tab generate a cloud and see both pairs highlighted; in the benchmark tab run the size sweep to compare the O(n²) and O(n log n) strategies and read off their crossover.