Closest Pair of Points Algorithms

Martin Rau 📧 and Tobias Nipkow 🌐

January 13, 2020

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

This entry provides two related verified divide-and-conquer algorithms solving the fundamental Closest Pair of Points problem in Computational Geometry. Functional correctness and the optimal running time of O(n log n) are proved. Executable code is generated which is empirically competitive with handwritten reference implementations.
BSD License

Change history

April 14, 2020

Incorporate Time_Monad of the AFP entry Root_Balanced_Tree.

Topics

Related Publications

Theories of Closest_Pair_Points