Rabin's Closest Pair of Points Algorithm (Q7361190)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Randomized_Closest_Pair
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Rabin's Closest Pair of Points Algorithm |
AFP entry Randomized_Closest_Pair |
Statements
8 September 2024
0 references
Emin Karayel
0 references
Zixuan Fan
0 references
Rabin's Closest Pair of Points Algorithm (English)
0 references
This entry formalizes Rabin’s randomized algorithm for the closest pair of points problem with expected linear running time. Remarkable is that the best-known deterministic algorithms have super-linear running times. Hence this algorithm is one of the first known examples of randomized algorithms that outperform deterministic algorithms. The formalization also introduces a probabilistic time monad, which builds on the existing deterministic time monad.
0 references
