Brute Force | Neighbors | Quadtree | Conga Line | MultiConga | FastPair | |
n = 250 | 2.73s | 0.16s | 0.19s | 0.25s | 0.12s | 0.12s |
500 | 21.76s | 0.65s | 0.90s | 1.29s | 0.50s | 0.46s |
1000 | 173.91s | 2.64s | 4.18s | 6.20s | 2.03s | 1.89s |
2000 | 1402.60s | 10.80s | 28.94s | 8.45s | 7.72s | |
4000 | 44.43s | 167.86s | 34.87s | 31.97s | ||
8000 | 179.94s | 598.28s | 142.23s | 131.21s | ||
16000 | 762.80s | 2818.09s | 600.74s | 556.67s | ||
32000 | 3130.31s | 2485.36s | 2223.75s |
Greedy matching was performed on distance matrices constructed at random. Distances were computed on the fly by using indices as seeds to a random number generator, so the matrix did not need to be stored in core. Times are averages over ten runs. The quadtree data structure was only run on data sets of 1000 or fewer points due to its high storage requirements. Code was written in C++, compiled and optimized by Metrowerks Codewarrior 10, and run on a 200MHz PowerPC 603e processor (Apple Powerbook 3400c).