文章基本信息

标题：Computing Opaque Interior Barriers à la Shermer
本地全文：下载
作者：Adrian Dumitrescu ; Minghui Jiang ; Csaba D. T{\'o}th 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：28
页码：128-143
DOI：10.4230/LIPIcs.APPROX-RANDOM.2014.128
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given polygon was initiated by Mazurkiewicz in 1916. Such a collection forms an opaque barrier for the polygon. In 1991 Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex n-gon. He conjectured that the barrier found by his algorithm is optimal, however this was refuted recently by Provan et al. Here we give a Shermer like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in O(n) time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm.
关键词：Opaque barrier; approximation algorithm; isoperimetric inequality