Finding the \(\Theta \)-guarded region
type: Item
instance of: scholarly article
title: Finding the \(\Theta \)-guarded region
zbMATH Open document ID: 1192.65025
author: Domagoj Matijević
author: Ralf Osbild
published in: Computational Geometry
publication date: 2009-11-16T00:00:00Z
review text: Let \(G\) be a finite set of \(n\) points (guards) in \(\mathbb R^2\). A \(\Theta\)-cone is a cone with apex angle \(\Theta\). A \(\Theta\)-cone is called empty with respect to \(G\) if it does not contain any point of \(G\) in its interior. A point \(p \in \mathbb R^2\) is called \(\Theta\)-guarded if every \(\Theta\)-cone with its apex located at \(p\) is non-empty. Further, the set of all \(\Theta\)-guarded points is the \(\Theta\)-region. In this paper, the structure of the boundary of the \(\Theta\)-region is described for different values of \(\Theta\). For \(\Theta \geq \pi\), an efficient \({\mathcal O} (n \log n)\) algorithm is presented to compute this boundary. For \(\Theta < \pi\), it is shown that the boundary of a \(\Theta\)-region is contained in an arrangement of circular arcs whose number is bounded by \({\mathcal O}({n\over \Theta})\). For \(\Theta \geq \pi/2\), the complexity of the \(\Theta\)-region is \({\mathcal O}(n)\). Finally, an algorithm is given to compute the \(\Theta\)-region in \({\mathcal O}(n^{3/2+\xi}/\Theta + \mu \log n)\) time for any \(\xi > 0\), where \(\mu \) denotes the complexity of the arrangement of the \({\mathcal O}(n/\Theta)\) arcs.
reviewed by: Gerlind Plonka
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 5633801
zbMATH Keywords: \(\Theta\)-guarded region
zbMATH Keywords: unoriented \(\Theta\)-maxima
zbMATH Keywords: convex hull generalization
zbMATH Keywords: good \(\Theta\)-illumination
zbMATH Keywords: \(\alpha\)-embracing contour
zbMATH Keywords: boundary
zbMATH Keywords: algorithm
MaRDI profile type: Publication
full work available at URL: j.comgeo.2009.07.001
OpenAlex ID: W1516616229
cites work: Unoriented $Theta$-Maxima in the Plane: Complexity and Algorithms
cites work: Algorithms for Reporting and Counting Geometric Intersections
cites work: On the convex layers of a planar set
cites work: A combinatorial theorem in plane geometry
cites work: On k-Hulls and Related Problems
cites work: Arrangements of curves in the plane --- topology, combinatorics, and algorithms
cites work: On the shape of a set of points in the plane
cites work: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
cites work: Efficient partition trees
cites work: Q3799261
cites work: Q3992847
cites work: Q4945523
DOI: 10.1016/J.COMGEO.2009.07.001
description: scientific article; zbMATH DE number 5633801