## Abstract

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 [12]. 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.

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

Pages | 136-140 |

Number of pages | 5 |

State | Published - 2015 |

Externally published | Yes |

Event | 27th Canadian Conference on Computational Geometry, CCCG 2015 - Kingston, Canada Duration: Aug 10 2015 → Aug 12 2015 |

### Other

Other | 27th Canadian Conference on Computational Geometry, CCCG 2015 |
---|---|

Country | Canada |

City | Kingston |

Period | 8/10/15 → 8/12/15 |

## ASJC Scopus subject areas

- Geometry and Topology
- Computational Mathematics