Simple randomized algorithms for closest pair problems
| Autor: | Golin, M., Raman, R., Schwarz, C., Smid, M. |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 1992 |
| Zdroj: | Research Report |
| Popis: | We present a conceptually simple, randomized incremental algorithm for finding the closest pair in a set of $n$ points in $D$-dimensional space, where $D \geq 2$ is a fixed constant. Using dynamic perfect hashing, the algorithm runs in $O(n)$ expected time. In addition to being quick on the average, this algorithm is reliable: we show that it runs in $O(n \log n / \log\log n)$ time with high probability. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|