Computer Science – Computational Geometry
Scientific paper
2010-05-12
Computer Science
Computational Geometry
18 pages, 7 figures. This version replaces the previous version from July 2010
Scientific paper
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 {\em opaque set} or a {\em 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 + \frac{2 +\sqrt{2}}{\pi}=1.5867...$. For connected barriers we achieve the approximation ratio 1.5716, while for single-arc barriers we achieve the approximation ratio $\frac{\pi+5}{\pi+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.
Dumitrescu Adrian
Jiang Minghui
pach János
No associations
LandOfFree
Opaque sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Opaque sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Opaque sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-640094