# 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.

**MPI-I-94-149**. September** **1994, 14 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-94-149.pdf | 63 KBytes; 193 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://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},`

`}`