Test of Closest Pair Data Structures

Most Expensive Insertion for Rectilinear Max-TSP

Brute Force Neighbors Quadtree Conga Line MultiConga FastPair
n = 250 6.84s 3.69s 0.37s 2.24s 0.79s 1.44s
500 56.64s 27.23s 1.83s 11.15s 3.92s 9.76s
1000 481.97s 226.55s 8.47s 57.32s 21.43s 81.19s
2000 7452.00s 2661.73s   328.68s 155.65s 870.60s
4000       1446.53s 634.06s  
8000         4130.86s  

Traveling salesman tours were formed by repeatedly adding the point that makes the augmented tour longest. 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).