Grid structures for efficient geometric algorithms

For the on-line version of the closest pair problem, the points become available one after another. A new point arrives as soon as the insertion of the previous point has been completed. At the start of the algorithm, the final size of the point set is not known. To solve this on-line problem, we ne...

Full description

Saved in:
Bibliographic Details
Main Authors: Xiaodong Wang, Daxin Zhu, Yingjie Wu
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Binary search trees
computational geometry
dynamic data structures
Handheld computers
Heuristic algorithms
on-line algorithms
Search problems
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For the on-line version of the closest pair problem, the points become available one after another. A new point arrives as soon as the insertion of the previous point has been completed. At the start of the algorithm, the final size of the point set is not known. To solve this on-line problem, we need a data structure that maintains the closest pair in the current point set in E d . The only operation to be supported is the insertion of a point. After an insertion, we have to update the closest pair. In high-dimension cases, a data structure is given that maintains the minimal distance in amortized O((log n) d-1 ) time, using O(n) space. This leads to an O(n log d-1 n) time algorithm for the on-line closest pair problem. This paper presents an efficient data structure for the on-line closest pair problem in d dimensional space. The data structure maintains the closest pair of the current point set in d dimensional space on-line in amortized time O(log 2 n), using O(n) space.
DOI:10.1109/ICINFA.2011.5949045