## Abstract

Given a set P of n moving points in fixed dimension d, where the trajectory of each point is a polynomial of degree bounded by some constant, we present a kinetic data structure (KDS) for maintenance of the closest pair on P. Assuming the closest pair distance is between 1 and Δ over time, our KDS uses O(nlog Δ) space and processes O(n^{2}βlog Δlog n+ n^{2}βlog Δlog log Δ) events, each in worst-case time O(log ^{2}n+ log ^{2}log Δ). Here, β is an extremely slow-growing function. The locality of the KDS is O(log n+ log log Δ). Our closest pair KDS supports insertions and deletions of points. An insertion or deletion takes worst-case time O(log Δlog ^{2}n+ log Δlog ^{2}log Δ). Also, we use a similar approach to provide a KDS for the all ε-nearest neighbors in R^{d}. The complexities of the previous KDSs, for both closest pair and all ε-nearest neighbors, have polylogarithmic factors, where the number of logs depends on dimension d. Assuming Δ is polynomial in n, our KDSs obtain improvements on the previous KDSs. Our solutions are based on a kinetic clustering on P. Though we use ideas from the previous clustering KDS by Hershberger, we simplify and improve his work.

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

Pages (from-to) | 2742-2756 |

Number of pages | 15 |

Journal | Algorithmica |

Volume | 80 |

Issue number | 10 |

DOIs | |

State | Published - Oct 1 2018 |

## Keywords

- All nearest neighbors
- Closest pair
- Clustering
- Kinetic data structure
- Moving points

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics