Finding the Θ-guarded region (CROSBI ID 168980)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Matijević, Domagoj ; Osbild, Ralf
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
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
43 (2)
2010.
207-218
objavljeno
0925-7721
10.1016/j.comgeo.2009.07.001