Opaque Sets

Dumitrescu, Adrian and Jiang, Minghui and Pach, János (2014) Opaque Sets. ALGORITHMICA, 69 (2). pp. 315-334. ISSN 0178-4617

Preview

Text 1005.2218v5.pdf Download (243kB) | Preview

Abstract

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 1/2+ 2 +√2/π=1.5867 ∈. For connected barriers we achieve the approximation ratio 1.5716, while for single-arc barriers we achieve the approximation ratio π+5/π+2 = 1.5834 ∈. 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. © 2012 Springer Science+Business Media New York.

Actions (login required)

Edit Item