The Maximum Cover for Passive Localisation
摘要
Imagine a polygon-shaped platform P and only one static spotlight outside P; which direction should the spotlight face to light most of P? This problem occurs in maximising the visibility, as well as in limiting the uncertainty in localisation problems. More formally, we define the following maximum cover problem: “Given a convex polygon P and a Field Of View (FOV) with a given centre and inner angle \(\phi \) ; find the direction (an angle of rotation \(\theta \) ) of the FOV such that the intersection between the FOV and P has the maximum area”. In this paper, we provide the theoretical foundation for the analysis of the maximum cover with a rotating field of view. Since the optimal solution is a real number, we develop an algorithm that approximates the direction of the field of view, with precision \(\varepsilon \) , and complexity \(\mathcal {O}(n(\log {n}+(\log {\varepsilon })/\phi ))\) .