Closest Pair Data Structures
: Experimental Data
These experiments compared six different
closest pair methods
on a variety of applications, with several different types of distance function.
Cheapest insertion heuristic for TSP of uniformly distributed points in
R
20
Most expensive insertion heuristic for rectilinear Max-TSP
Greedy matching of uniformly distributed points in
R
20
Greedy matching with random distance matrices
Greedy maximum matching for rectilinear point sets
Hierarchical clustering of uniformly distributed points in
R
20
Hierarchical clustering of points in a 31-dimensional fractal
Multifragment heuristic for rectilinear Max-TSP
Multifragment heuristic for TSP in
R
20
David Eppstein,
Information & Computer Science
,
UC Irvine
, .