Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Computational Mechanics
Distance Measure
Total Order
Subscribe
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
Edit
Lazy Algorithms for Dynamic Closest Pair with Arbitary Distance Measures
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Jean Cardinal
,
David Eppstein
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 wellstudied, 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.
Conference:
Algorithm Engineering and Experimentation  ALENEX
, pp. 112119, 2004
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.
(
www.informatik.unitrier.de
)
References
(8)
Experiments on traveling salesman heuristics
(
Citations: 60
)
Jon Louis Bentley
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 9199, 1990
An Optimal Algorithm for ClosestPair Maintenance
(
Citations: 41
)
Sergei Bespamyatnikh
Journal:
Discrete & Computational Geometry  DCG
, vol. 19, no. 2, pp. 175195, 1998
Algorithms for dynamic closest pair and n body potential fields
(
Citations: 39
)
Paul B. Callahan
,
S. Rao Kosaraju
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 263272, 1995
Lazy Algorithms for Dynamic Closest Pair with Arbitrary Distance Measures
(
Citations: 6
)
Jean Cardinal
,
David Eppsteiny
Published in 2003.
A clustering algorithm for entropyconstrained vector quantizer design with applications in coding image pyramids
(
Citations: 20
)
Diego P. De Garrido
,
William A. Pearlman
,
Weiler A. Finamore
Journal:
IEEE Transactions on Circuits and Systems for Video Technology  TCSV
, vol. 5, no. 2, pp. 8395, 1995
Sort by:
Citations
(1)
Continuous Monitoring of Exclusive Closest Pairs
(
Citations: 4
)
Leong Hou U
,
Nikos Mamoulis
,
Man Lung Yiu
Conference:
Symposium on Large Spatial Databases  SSD
, pp. 119, 2007