Finding the \(\Theta \)-guarded region (Q1037785)

Let \(G\) be a finite set of \(n\) points (guards) in \(\mathbb R^2\). A \(\Theta\)-cone is a cone with apex angle \(\Theta\). A \(\Theta\)-cone is called empty with respect to \(G\) if it does not contain any point of \(G\) in its interior. A point \(p \in \mathbb R^2\) is called \(\Theta\)-guarded if every \(\Theta\)-cone with its apex located at \(p\) is non-empty. Further, the set of all \(\Theta\)-guarded points is the \(\Theta\)-region. In this paper, the structure of the boundary of the \(\Theta\)-region is described for different values of \(\Theta\). For \(\Theta \geq \pi\), an efficient \({\mathcal O} (n \log n)\) algorithm is presented to compute this boundary. For \(\Theta < \pi\), it is shown that the boundary of a \(\Theta\)-region is contained in an arrangement of circular arcs whose number is bounded by \({\mathcal O}({n\over \Theta})\). For \(\Theta \geq \pi/2\), the complexity of the \(\Theta\)-region is \({\mathcal O}(n)\). Finally, an algorithm is given to compute the \(\Theta\)-region in \({\mathcal O}(n^{3/2+\xi}/\Theta + \mu \log n)\) time for any \(\xi > 0\), where \(\mu \) denotes the complexity of the arrangement of the \({\mathcal O}(n/\Theta)\) arcs.