Seminar

Speaker:	Evangelos Kranakis (Professor, School of Computer Science, Carleton University, Ottawa)
Title:	Monitoring the Plane with Rotating Radars
Date:	Friday, 17 May 2013
Time:	18:30-19:30
Location:	Univeristy of Athens, Department of Mathematics, University of Athens, room Γ33

Abstract

Consider an arbitrary set P of n points in the plane and suppose that a radar is located at each point in P. The radars are rotating perpetually (around their centre) with identical constant speeds, continuously emitting a half-infinite light ray. A radar can ``locate'' (detect) any object in the plane when its light ray is incident to the object. Motivated from the basic idea of radar radio echo-location we propose a new model suitable for monitoring the plane. For any initial orientation of the light rays and any point p in the plane, we define the idle time of p, as the maximum time that p is unattended by any of the radars. We are interested in studying the following monitoring problem: What should the initial orientation of the n radar rays be so as to minimize the maximum idle time of any point in the plane? We propose algorithms for specifying the initial orientations of the radar rays and prove various bounds on the idle time depending on the type of configuration of n points P in the plane. We study interesting time/beam-width tradeoffs involving arbitrary pointsets and deterministic and randomized algorithms.