Finding the Θ-guarded region

We are given a finite set of n points (guards) G in the plane R2 and an angle 0⩽Θ⩽2π. A Θ-cone is a cone with apex angle Θ. We call a Θ-cone empty (with respect to G) if it does not contain any point of G. A point p∈R2 is called Θ-guarded if every Θ-cone with its apex located at p is non-empty. Furthermore, the set of all Θ-guarded points is called the Θ-guarded region, or the Θ-region for short.We present several results on this topic. The main contribution of our work is to describe the Θ-region with circular arcs, and we give an algorithm to compute it. We prove a tight O(n) worst-case bound on the complexity of the Θ-region for . In case Θ is bounded from below by a positive constant, we prove an almost linear bound O(n1+ε) for any ε>0 on the complexity. Moreover, we show that there is a sequence of inputs such that the asymptotic bound on the complexity of their Θ-region is Ω(n2).