Abstract
We study some geometric optimal hitting set (stabbing) problems involving certain classes of objects in the plane. The objects include axis-parallel line segments, red/blue sets of pseudo-segments, axis-parallel 2-link “L” chains, pairs of line segments, etc. We examine cases in which the objects are constrained so that at least one endpoint of each object is on an inclined line (a line with slope \(-1\)). We prove that stabbing a set of vertical segments using a minimum number of horizontal segments is NP-hard when the input segments are each touching the inclined line, possibly from both sides of the line. Previously, the problem was known to be NP-hard for the general version, stabbing vertical segments with a minimum number of horizontal segments in the plane [9], and for a constrained version of this problem, in which all of the vertical segments intersect a horizontal line [3]. We provide some constant factor approximation algorithms as well. In particular, we present a PTAS for this problem using the local search technique. In contrast, if both vertical and horizontal segments are touching the inclined line from exactly one side, then the problem can be solved in polynomial time. We prove that stabbing a class of 2-link chains (“Ί-chains”) by horizontal segments is NP-hard, when both the chains and the segments have an endpoint on an inclined line and lie on one side (say, the right side) of the line. Finally, we prove that stabbing pairs of segments (each pair contains either two vertical segments or one vertical and one horizontal segments) by horizontal segments is NP-hard, when the segments are touching the inclined line from only one side.
J. S. B. Mitchell—Partially supported by the National Science Foundation (CCF-1526406), the US-Israel Binational Science Foundation (project 2016116), and DARPA (Lagrange).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Several proofs are deferred to the full paper, because of page limitations here.
References
Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B., Simakov, M.: Selecting and covering colored points. Discret. Appl. Math. 250, 75–86 (2018)
Bandyapadhyay, S., Maheshwari, A., Mehrabi, S., Suri, S.: Approximating dominating set on intersection graphs of rectangles and L-frames. In: MFCS, pp. 37:1–37:15 (2018)
Bandyapadhyay, S., Mehrabi, S.: Constrained orthogonal segment stabbing. CoRR abs/1904.13369 (2019). Proceedings of the CCCG 2019, Edmonton, Canada, pp. 195–202
de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(03), 187–205 (2012)
Chan, T.M., Grant, E.: Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom. 47(2), 112–124 (2014)
Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discret. Comput. Geom. 48(2), 373–392 (2012)
Chepoi, V., Felsner, S.: Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. Comput. Geom. 46(9), 1036–1041 (2013)
Correa, J.R., Feuilloley, L., Pérez-Lantero, P., Soto, J.A.: Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity. Discret. Comput. Geom. 53(2), 344–365 (2015)
Katz, M.J., Mitchell, J.S.B., Nir, Y.: Orthogonal segment stabbing. Comput. Geom. Theory Appl. 30(2), 197–205 (2005)
Mudgal, A., Pandit, S.: Covering, hitting, piercing and packing rectangles intersecting an inclined line. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 126–137. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26626-8_10
Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discret. Comput. Geom. 44(4), 883–895 (2010)
Pandit, S.: Dominating set of rectangles intersecting a straight line. In: Canadian Conference on Computational Geometry, CCCG, pp. 144–149 (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Mitchell, J.S.B., Pandit, S. (2019). New Results on a Family of Geometric Hitting Set Problems in the Plane. In: Li, Y., Cardei, M., Huang, Y. (eds) Combinatorial Optimization and Applications. COCOA 2019. Lecture Notes in Computer Science(), vol 11949. Springer, Cham. https://doi.org/10.1007/978-3-030-36412-0_31
Download citation
DOI: https://doi.org/10.1007/978-3-030-36412-0_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-36411-3
Online ISBN: 978-3-030-36412-0
eBook Packages: Computer ScienceComputer Science (R0)