Advertisement
Published in:
2011 | OriginalPaper | Chapter
Opaque Sets
Authors : Adrian Dumitrescu, Minghui Jiang, János Pach
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The problem of finding “small” sets that meet every straight-line which intersects a given convex region was initiated by Mazurkiewicz in 1916. We call such a set an
opaque set
or a
barrier
for that region. We consider the problem of computing the shortest barrier for a given convex polygon with
n
vertices. No exact algorithm is currently known even for the simplest instances such as a square or an equilateral triangle. For general barriers, we present a
O
(
n
) time approximation algorithm with ratio
$\frac{1}{2}+ \frac{2 +\sqrt{2}}{\pi}=1.5867\ldots$
. For connected barriers, we can achieve the approximation ratio
$\frac{\pi+5}{\pi+2} =1.5834\ldots$
again in
O
(
n
) time. We also show that if the barrier is restricted to the interior and the boundary of the input polygon, then the problem admits a fully polynomial-time approximation scheme for the connected case and a quadratic-time exact algorithm for the single-arc case. These are the first approximation algorithms obtained for this problem.