Monitoring the Plane with Rotating Radars

Authors: J Czyzowicz S Dobrev B Joeris E Kranakis D Krizanc J Maňuch O MoralesPonce J Opatrny L Stacho J Urrutia

Publish Date: 2015/02/26

Volume: 31, Issue: 2, Pages: 393-405

PDF Link

Abstract

Consider a set P of n points in the plane and n radars located at these points The radars are rotating perpetually around their centre with identical constant speeds continuously emitting pulses of radio waves modelled as halfinfinite rays A radar can “locate” or detect any object in the plane eg using radio echolocation when its ray is incident to the object We propose a model for monitoring the plane based on a system of radars For 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 study the following monitoring problem what should the initial direction 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 directions of the radar rays and prove bounds on the idle time depending on the type of configuration of n points For arbitrary sets P we give a On log n time algorithm guaranteeing a O1/sqrtn upper bound on the idle time and a On6/ln 3 n time algorithm with associated O log n/ n upper bound on the idle time For a convex set P we show a On log n time algorithm with associated O1/n upper bound on the idle time Further for any set P of points if the radar rays are assigned a direction independently at random with the uniform distribution then we can prove a tight varTheta ln n /n upper and lower bound on the idle time with high probability

Keywords: