Closest & Farthest Pair of Points

Practice 3 for the Advanced Algorithms course (21747) at the Universitat de les Illes Balears. A Java Swing application, on a Model–View–Controller architecture, that finds the closest and the farthest pair of points in a randomly generated 2D cloud, and compares a brute-force strategy against a divide & conquer one both visually and through a benchmark.

The problem

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.

About

• 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 practice on, a dedicated Reporter mediates all cross-package messages; the controller owns generation, execution and benchmarking, and the view only renders snapshots.

Executing the project

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.