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).