Test of Closest Pair Data Structures

Rectilinear Greedy Maximum-Weight Matching

Brute Force Neighbors Quadtree Conga Line MultiConga FastPair
n = 250 0.81s 0.92s 0.14s 0.03s 0.04s 0.03s
500 6.65s 7.43s 0.78s 0.16s 0.15s 0.14s
1000 55.54s 65.08s 3.57s 0.72s 0.69s 0.67s
2000 492.97s 552.08s   3.22s 3.13s 3.02s
4000       13.36s 13.20s 12.87s
8000       58.92s 60.08s 59.76s
16000       264.92s 289.49s 298.05s
32000       1136.59s 1273.68s 1367.93s

Matching was performed by repeatedly finding and removing the two farthest-apart points. Points were placed uniformly at random in the unit square. 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).