Finding the theta-Guarded Region
| dc.creator | Matijević, Domagoj | |
| dc.creator | Osbild, Ralf | |
| dc.date | 2008-06-12 | |
| dc.date | 2008-09-11 | |
| dc.date.accessioned | 2026-07-07T10:01:53Z | |
| dc.date.available | 2026-07-07T10:01:53Z | |
| dc.description | 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. | |
| dc.description | 21 pages, 13 figures; revised version with new results | |
| dc.identifier | https://arxiv.org/abs/0806.2090 | |
| dc.identifier | http://arxiv.org/abs/0806.2090 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168780 | |
| dc.subject | Computational Geometry | |
| dc.title | Finding the theta-Guarded Region | |
| dc.type | text |