## Abstract

Given a set of n moving points in R^{d}, where each point moves along a linear trajectory at arbitrary but constant velocity, we present an O˜(n^{5/3})-time algorithm^{1} 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˜(n^{5/3}) space and O˜(n^{2/3}) query time, O˜(n^{5}) space and polylogarithmic query time, or O˜(n) space and O˜(n^{4/5}) query time, for any constant ϵ>0 and any constant dimension d. The notation O˜ is used to hide polylogarithmic factors. That is, O˜(f(n))=O(f(n)log^{c}n), where c is a constant.

Original language | English (US) |
---|---|

Pages (from-to) | 2-7 |

Number of pages | 6 |

Journal | Computational Geometry: Theory and Applications |

Volume | 60 |

DOIs | |

State | Published - Jan 1 2017 |

Externally published | Yes |

## Keywords

- Closest pair distance
- Kinetic algorithms
- Linearly moving points
- Nearest neighbor distances
- Nearest neighbor search

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics