Test of Closest Pair Data Structures

Greedy matching in R20

Brute Force Neighbors Quadtree Conga Line MultiConga FastPair
n = 250 3.08s 0.24s 0.20s 0.31s 0.16s 0.15s
500 27.12s 1.04s 1.01s 1.67s 0.68s 0.63s
1000 241.97s 4.40s 4.56s 8.45s 2.93s 2.76s
2000 2087.87s 20.13s   47.53s 14.38s 12.93s
4000   94.73s   243.21s 66.59s 61.39s
8000   376.15s   1136.30s 282.53s 256.44s
16000   1524.35s     1171.30s 1072.35s

Greedy matching was performed on points placed uniformly at random in the unit hypercube. Times include only the construction of the closest pair data structure and algorithm execution (not the initial point placement) and 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).