Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:06:27 PM
Last modification on : Thursday, October 27, 2022 - 4:02:53 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 4:38:52 PM


  • 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⟩



Record views


Files downloads