Academic
Publications
Lazy Algorithms for Dynamic Closest Pair with Arbitary Distance Measures

Lazy Algorithms for Dynamic Closest Pair with Arbitary Distance Measures,Jean Cardinal,David Eppstein

Lazy Algorithms for Dynamic Closest Pair with Arbitary Distance Measures   (Citations: 1)
BibTex | RIS | RefWorks Download
Abstract We propose novel lazy algorithms for the dynamic,closest pair problem,with arbitrary distance measures. In this problem,we have to maintain the closest pair of points under insertion and deletion operations, where the distance between two points must be symmetric,and take value in a totally ordered set. Many geometric special cases of this problem are well-studied, but only few algorithms are known when the distance measure is arbitrary. The proposed algorithms use a simple delayed computation mechanism to spare distance calculations, and one of these algorithms is a lazy version of the FastPair algorithm recently proposed by Eppstein. Experimental results on a wide number of applications show that lazy FastPair performs signican tly better than FastPair and the other algorithms we tested.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: