Computer Science – Computational Geometry
Scientific paper
2008-06-12
Computer Science
Computational Geometry
21 pages, 13 figures; revised version with new results
Scientific paper
We are given a finite set of n points (guards) G in the plane R^2 and an angle 0 < theta < 2 pi. A theta-cone is a cone with apex angle theta. We call a theta-cone empty (with respect to G) if it does not contain any point of G. A point p in R^2 is called theta-guarded if every theta-cone with its apex located at p is non-empty. Furthermore, the set of all theta-guarded points is called the theta-guarded region, or the theta-region for short. We present several results on this topic. The main contribution of our work is to describe the theta-region with O(n/theta) circular arcs, and we give an algorithm to compute it. We prove a tight O(n) worst-case bound on the complexity of the theta-region for theta >= pi/2. In case theta is bounded from below by a positive constant, we prove an almost linear bound O(n^(1+epsilon)) for any epsilon > 0 on the complexity. Moreover, we show that there is a sequence of inputs such that the asymptotic bound on the complexity of their theta-region is Omega(n^2). In addition we point out gaps in the proofs of a recent publication that claims an O(n) bound on the complexity for any constant angle theta.
Matijević Domagoj
Osbild Ralf
No associations
LandOfFree
Finding the theta-Guarded Region does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finding the theta-Guarded Region, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding the theta-Guarded Region will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-690975