# Queries on Voronoi Diagrams of Moving Points

1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Suppose we are given n moving postmen described by their motion equations pi(t) = si + vi t, i=1, ... , n, where si belongs to R2 is the position of the i'th postman at time t=0, and vi in R2 is his velocity. The problem we address is how to preprocess the postmen data so as to be able to efficiently answer two types of nearest-neighbor queries. The first one asks who is the nearest postman at time tq to a dog located at point sq. In the second type a query dog is located at point sq at time tq, its speed is vq>|vi| (for all i=1, ... , n), and we want to know which postman the dog can catch first. The first type of query is relatively simple to address, the second type at first seems much more complicated. We show that the problems are very closely related, with efficient solutions to the first type of query leading to efficient solutions to the second. We then present two solutions to these problems, with tradeoff between preprocessing time and query time. Both solutions use deterministic data structures.
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 1996, 6, pp.315-327

https://hal.inria.fr/inria-00413168
Contributeur : Olivier Devillers <>
Soumis le : jeudi 3 septembre 2009 - 13:34:00
Dernière modification le : jeudi 11 janvier 2018 - 16:57:39
Document(s) archivé(s) le : mardi 15 juin 2010 - 23:08:02

### Fichier

dgks-qvdmp-96.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00413168, version 1

### Citation

Olivier Devillers, Mordecai Golin, Klara Kedem, Stefan Schirra. Queries on Voronoi Diagrams of Moving Points. Computational Geometry, Elsevier, 1996, 6, pp.315-327. 〈inria-00413168〉

### Métriques

Consultations de la notice

## 220

Téléchargements de fichiers