Paper Info
Title
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity.
Abstract
We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line segments of minimum total length so that every rectangle is stabbed by some line segment. A line segment stabs a rectangle if it intersects its left and its right boundary. The problem, which we call Stabbing, can be motivated by a resource allocation problem and has applications in geometric network design. To the best of our knowledge, only special cases of this problem have been considered so far. is a weighted geometric set cover problem, which we show to be NP-hard. A constrained variant of Stabbing turns out to be even APX-hard. While for general set cover the best possible approximation ratio is $Theta(log n)$, it is an important field in geometric approximation algorithms to obtain better ratios for geometric set cover problems. Chan et al. [SODAu002712] generalize earlier results by Varadarajan [STOCu002710] to obtain sub-logarithmic performances for a broad class of weighted geometric set cover instances that are characterized by having low shallow-cell complexity. The shallow-cell complexity of Stabbing instances, however, can be high so that a direct application of the framework of Chan et al. gives only logarithmic bounds. We still achieve a constant-factor approximation by decomposing general instances into what we call laminar instances that have low enough complexity. Our decomposition technique yields constant-factor approximations also for the variant where rectangles can be stabbed by horizontal and vertical segments and for two further geometric set cover problems.
Year
DOI
Venue
2018
10.4230/LIPIcs.ISAAC.2018.61
ISAAC
DocType
Volume
Issue
Conference
abs/1806.02851
123
Citations 
PageRank 
References 
0
0.34
3
Authors
5
Name
Order
Citations
PageRank
Timothy M. Chan12033150.55
Thomas C. van Dijk2639.52
Krzysztof Fleszar336825.38
Joachim Spoerhase411214.12
Alexander Wolff522222.66