Test of Closest Pair Data Structures

Cheapest insertion heuristic in R20

Brute Force Neighbors Quadtree Conga Line MultiConga FastPair
n = 250 18.31s 1.57s 0.67s 5.00s 1.16s 1.00s
500 156.96s 6.83s 3.09s 24.15s 5.01s 4.26s
1000 1279.79s 29.72s 13.60s 113.52s 21.34s 18.17s
2000   129.61s   545.68s 94.75s 78.52s
4000   574.86s   2705.35s 412.70s 343.53s
8000   2403.71s     1808.10s 1430.10s

A traveling salesman tour was formed by repeatedly adding vertices, at each step making the resulting tour as short as possible. Points were 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).