The following algorithms and applications can be implemented efficiently
using our new closest pair data structures, or involve closest pair
computation as important subroutines.
- Dynamic minimum spanning trees
- Two-optimization heuristics in combinatorial optimization
- Straight skeletons and roof design
- Ray-intersection diagram
- Other collision detection applications
- Hierarchical clustering
- Traveling salesman heuristics
- Greedy matching
- Constructive induction
- Gröbner bases
David Eppstein,
Information & Computer Science,
UC Irvine,
.