engleski

Finding the Θ-guarded region

We are given a finite set of n points (guards) G in the plane 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 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(n^{; ; ; ; 1+ε}; ; ; ; ) 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 Ω(n^2).

Θ-guarded region; Unoriented Θ-maxima; Convex hull generalization; Good Θ-illumination; α-embracing contour

nije evidentirano