English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Revenge of the dog: queries on Voronoi diagrams of moving points

MPS-Authors
/persons/resource/persons44509

Golin,  Mordecai J.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45391

Schirra,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-94-149.pdf
(Any fulltext), 193KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Devillers, O., Golin, M. J., Schirra, S., & Kedem, K.(1994). Revenge of the dog: queries on Voronoi diagrams of moving points (MPI-I-94-149). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B535-4
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 efficientMailly 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 fast query dog is located a point $s_q$ at time $t_q$, its velocity is $v_q$ where $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. Both solutions use deterministic data structures.