Monitoring the Plane with Rotating Radars

作者：Czyzowicz J; Dobrev S; Joeris B; Kranakis E; Krizanc D; Manuch J; Morales Ponce O^*; Opatrny J; Stacho L; Urrutia J

来源：Graphs and Combinatorics, 2015, 31(2): 393-405.

DOI：10.1007/s00373-015-1543-4

• Convex
• Detection
• Idle time
• Monitor
• Orientation
• Patrol
• Plane
• Points
• Radar
• Random
• (Light) Ray

Consider a set of points in the plane and 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 half-infinite rays). A radar can "locate" (or detect) any object in the plane (e.g., using radio echo-location 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 in the plane, we define the idle time of , as the maximum time that is "unattended" by any of the radars. We study the following monitoring problem: what should the initial direction of the 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 points. For arbitrary sets we give a time algorithm guaranteeing a upper bound on the idle time, and a time algorithm with associated upper bound on the idle time. For a convex set , we show a time algorithm with associated upper bound on the idle time. Further, for any set of points if the radar rays are assigned a direction independently at random with the uniform distribution then we can prove a tight upper and lower bound on the idle time with high probability.

• 出版日期2015-3