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 q₀and time t₀who is the nearest postman to q₀at time t₀? We present a randomized incremental data structure that answers the query in expected O( log²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 v_dcould 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²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 O( log³n).