MPI-INF/SWS Research Reports 1991-2021

# MPI-I-94-149

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

### Devillers, O. and Golin, Mordecai and Schirra, Stefan and Kedem, K.

#### September 1994, 14 pages.

.
##### Status: available - back from printing

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.

• MPI-I-94-149.pdf
• Attachement: MPI-I-94-149.ps.gz (63 KBytes); MPI-I-94-149.pdf (193 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-149

BibTeX
@TECHREPORT{DevillersGolinSchirraKedern94,
AUTHOR = {Devillers, O. and Golin, Mordecai and Schirra, Stefan and Kedem, K.},
TITLE = {Revenge of the dog: queries on Voronoi diagrams of moving points},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-94-149},
MONTH = {September},
YEAR = {1994},
ISSN = {0946-011X},
}