Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points

Olivier Devillers 1 Mordecai Golin 1 Klara Kedem 1 Stefan Schirra 1
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 $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i \in \R^2$ 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 $t_q$ to a dog located at point $s_q$?''. In the second type a query dog is located a point $s_q$ at time $t_q$, its velocity is $v_q>|v_i|$ (for all $i=1, \ldots , n$), and we want to know which postman the dog can catch first. We present two solutions to these problems, with tradeoff between preprocessing time and query time. Both solutions use deterministic data structures.
Type de document :
[Research Report] RR-2329, INRIA. 1994
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:06:27
Dernière modification le : samedi 27 janvier 2018 - 01:30:56
Document(s) archivé(s) le : mardi 12 avril 2011 - 16:38:52



  • HAL Id : inria-00074345, version 1



Olivier Devillers, Mordecai Golin, Klara Kedem, Stefan Schirra. Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points. [Research Report] RR-2329, INRIA. 1994. 〈inria-00074345〉



Consultations de la notice


Téléchargements de fichiers