Opaque Sets

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 an approximation algorithm with ratio . For connected barriers we achieve the approximation ratio 1.5716, while for single-arc barriers we achieve the approximation ratio . All three algorithms run 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.


Published in:
Algorithmica, 69, 2, 315-334
Year:
2014
Publisher:
New York, Springer
ISSN:
0178-4617
Keywords:
Laboratories:




 Record created 2014-05-19, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)