pith. sign in

arxiv: 0809.0159 · v1 · submitted 2008-09-01 · 💻 cs.CG

Improved Approximations for Guarding 1.5-Dimensional Terrains

K. Elbassioni , D. Matijevic , J. Mestre , D. Severdija This is my paper
classification 💻 cs.CG
keywords problemalgorithmapproximationterrainanalysisapproximationsbalancedbasic
0
0 comments X
read the original abstract

We present a 4-approximation algorithm for the problem of placing a fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5. Our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Learning to Place Guards by Reinforcement: A Geo-Free Neural Policy for the Vertex-Guard Art Gallery Problem

    cs.LG 2026-06 unverdicted novelty 7.0

    A reinforcement learning policy for the vertex-guard art gallery problem encodes sufficient geometric information in its encoder to allow a simple classifier to achieve high coverage feasibility out of distribution.