Dog bites postman: point location in the moving Voronoi diagram and related problems

Abstract : In this paper, we discuss two variations of the two-dimensional post-office problem that arise when the post-offices are n postmen moving with constant velocities. The first variation addresses the question: given a point go and time to who is the nearest postman to go at time to? We present a randomized incremental data structure that answers the query in expected 0(log^2 n.) time. The second variation views a query point as a dog searching for a postman to bite and finds the postman that a dog running with speed Vd could reach first. While it is quite straightforward to design a data structure for the first problem, designing one for the second appears more difficult. We show that if the dog is quicker than all of the postmen then there is a nice correspondence between the problems. This correspondence will permit us to use the data structure developed for the first problem to solve the second one in O(log^2 n) time as well. The proposed structure is semi-dynamic, that is the set of postmen can be modified by inserting new postmen. A fully dynamic structure that also supports deletions can be obtained, but in that case the query time becomes 0(log^3 n).
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 1998, 8 (3), pp.321-342. 〈10.1142/S0218195998000163〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00795074
Contributeur : Olivier Devillers <>
Soumis le : mercredi 27 février 2013 - 11:17:00
Dernière modification le : samedi 27 janvier 2018 - 01:31:46

Identifiants

Collections

Citation

Olivier Devillers, Mordecai Golin. Dog bites postman: point location in the moving Voronoi diagram and related problems. International Journal of Computational Geometry and Applications, World Scientific Publishing, 1998, 8 (3), pp.321-342. 〈10.1142/S0218195998000163〉. 〈hal-00795074〉

Partager

Métriques

Consultations de la notice

232