Divide and conquer on points sorted by x: split, solve each half, then check a thin strip around the line, a few comparisons per point.
This interactive visualization needs JavaScript.