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 need a data structure that maintains the closest pair in the current point set in Ed.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 logd-1 n)time algorithm for the on-line closest pair problem.This paper presents an ef ficient 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.

作者: Xiaodong Wang Daxin Zhu Yingjie Wu

作者单位: Department of Computer Science Quanzhou Normal University Quanzhou,Fujian,China Department of Computer Science Fuzhou University Fuzhou,Fujian,China

会议类型: 国际会议

会议名称: 第八届IEEE信息与自动化国际会议(ICIC 2011)

会议地点: 深圳

会议语种:英文

页码: 506-508

在线出版日期: 2011-06-06（万方平台首次上网日期，不代表论文的发表时间）