Overview

A Java Swing application that finds the closest and farthest pair of points in a cloud, pitting a brute-force strategy against divide and conquer both visually and in a benchmark.

The closest pair can be had two ways: the naive double loop over every pair, or the classic divide and conquer that splits the plane, solves each half and only re-checks the points that fall inside the boundary strip. The farthest pair is a different shape of problem, since the two most distant points are always vertices of the convex hull, so it gets a quadratic baseline and a hull-based method.

The clouds are generated from a range of statistical distributions, because the crossover point where divide and conquer starts to win is not a constant: it depends on how the points are spread, which is exactly what the benchmark is there to show.

Project 3 of 7 for the Advanced Algorithms course at the Universitat de les Illes Balears, the one on divide and conquer.

javadivide-and-conquercomputational-geometry