Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
415413 | Computational Geometry | 2013 | 6 Pages |
Abstract
In this note, we present a simple combinatorial factor 6 algorithm for approximating the minimum hitting set of a family R={R1,…,Rn}R={R1,…,Rn} of axis-parallel rectangles in the plane such that there exists an axis-monotone curve γ that intersects each rectangle in the family. The quality of the hitting set is shown by comparing it to the size of a packing (set of pairwise non-intersecting rectangles) that is constructed along, hence, we also obtain a factor 6 approximation for the maximum packing of RR.In cases where the axis-monotone curve γ intersects the same side (e.g. the bottom side) of each rectangle in the family the approximation factor for hitting set and packing is 3.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Victor Chepoi, Stefan Felsner,