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.
- April 14, 2020
- Incorporate Time_Monad of the AFP entry Root_Balanced_Tree.
- Rau, M., & Nipkow, T. (2020). Verification of Closest Pair of Points Algorithms. Lecture Notes in Computer Science, 341–357. https://doi.org/10.1007/978-3-030-51054-1_20