Computing Opaque Interior Barriers à la Shermer

Authors Adrian Dumitrescu, Minghui Jiang, Csaba D. Tóth



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.128.pdf
  • Filesize: 0.61 MB
  • 16 pages

Document Identifiers

Author Details

Adrian Dumitrescu
Minghui Jiang
Csaba D. Tóth

Cite AsGet BibTex

Adrian Dumitrescu, Minghui Jiang, and Csaba D. Tóth. Computing Opaque Interior Barriers à la Shermer. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 128-143, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.128

Abstract

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.
Keywords
  • Opaque barrier
  • approximation algorithm
  • isoperimetric inequality

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail