کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949137 1439986 2017 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points
ترجمه فارسی عنوان
تقریبا نزدیک ترین فاصله جفت و نزدیکترین فاصله همسایه از نقاط خطی حرکت می کند
کلمات کلیدی
نزدیک ترین فاصله جفت، نزدیکترین فاصله همسایه، نزدیکترین همسایه جستجو، الگوریتم های جنبشی، نقاط به طور پیوسته حرکت می کند،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Given a set of n moving points in Rd, where each point moves along a linear trajectory at arbitrary but constant velocity, we present an O˜(n5/3)-time algorithm1 to compute a (1+ϵ)-factor approximation to the minimum closest pair distance over time, for any constant ϵ>0 and any constant dimension d. This addresses an open problem posed by Gupta, Janardan, and Smid [1].More generally, we consider a data structure version of the problem: for any linearly moving query point q, we want a (1+ϵ)-factor approximation to the minimum nearest neighbor distance to q over time. We present a data structure that requires O˜(n5/3) space and O˜(n2/3) query time, O˜(n5) space and polylogarithmic query time, or O˜(n) space and O˜(n4/5) query time, for any constant ϵ>0 and any constant dimension d.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 60, January 2017, Pages 2-7
نویسندگان
, ,