A clustering-based approach to kinetic closest pair

DOI10.1007/s00453-017-0338-9zbMath1391.68115OpenAlexW2640136065MaRDI QIDQ722518

Timothy M. Chan, Zahed Rahmati

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6050/

zbMATH Keywords

clusteringclosest pairkinetic data structureall nearest neighborsmoving points

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Cites Work

• Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points
• Optimal packing and covering in the plane are NP-complete
• Covering a set of points in multidimensional space
• Discrete mobile centers
• Smooth kinetic maintenance of clusters
• Almost optimal set covers in finite VC-dimension
• A simple, faster method for kinetic proximity problems
• Approximation schemes for covering and packing problems in image processing and VLSI
• Data Structures for Mobile Data
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• A Clustering-Based Approach to Kinetic Closest Pair

This page was built for publication: A clustering-based approach to kinetic closest pair