Daniel M. Khachay     (Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences; Ural Federal University, Ekaterinburg, Russian Federation)
Michael Yu. Khachay     (Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences; Ural Federal University, Ekaterinburg, Russian Federation)


The Hitting Set Problem (HSP) is the well known extremal problem adopting research interest in the fields of combinatorial optimization, computational geometry, and statistical learning theory for decades. In the general setting, the problem is NP-hard and hardly approximable. Also, the HSP remains intractable even in very specific geometric settings, e.g. for axis-parallel rectangles intersecting a given straight line. Recently, for the special case of the problem, where all the rectangles are unit squares, a polynomial but very time consuming optimal algorithm was proposed. We improve this algorithm to decrease its complexity bound more than 100 degrees of magnitude. Also, we extend it to the more general case of the problem  and show that the geometric HSP for axis-parallel (not necessarily unit) squares intersected by a line is polynomially solvable for any fixed range of squares to hit.


Hitting set problem, Dynamic programming, Computational geometry, Parameterized complexity.

Full Text:



  1. Brönnimann H. and Goodrich M. T. Almost optimal set covers in finite vc-dimension // Discrete & Computational Geometry, 1995. Vol. 14, no. 4. P. 463–479. DOI: 10.1007/BF02570718
  2. Chan T. M. Polynomial-time approximation schemes for packing and piercing fat objects // J. of Algorithms, 2003. Vol. 46, no. 2. P.178–189. DOI: 10.1016/S0196-6774(02)00294-8
  3. Chepoi V. and Felsner S. Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve // Computational Geometry, 2013. Vol. 46, no. 9. P. 1036–1041. DOI: 10.1016/j.comgeo.2013.05.008
  4. Correa J., Feuilloley L., Pérez-Lantero P. and Soto J. A. Independent and hitting sets of rectangles intersecting a diagonal line: Algorithms and complexity // Discrete & Computational Geometry, 2015. Vol. 53, no. 2. P. 344–365. DOI: 10.1007/s00454-014-9661-y
  5. Fowler R. J., Paterson M. S. and. Tanimoto S. L. Optimal packing and covering in the plane are np-complete // Information Processing Letters, 1981. Vol. 12, no. 3. P. 133–137. DOI: 10.1016/0020-0190(81)90111-3
  6. Haussler D. and Welzl E. Epsilon-nets and simplex range queries // Discrete & Computational Geometry, 1987. Vol. 2, no. 2. P. 127–151. DOI: 10.1007/BF02187876
  7. Hochbaum D.and Maass W. Approximation schemes for covering and packing problems in image processing and vlsi // J. ACM, 1985. Vol. 32, no. 1. P. 130–136. DOI: 10.1145/2455.214106
  8. Khachay M. Committee polyhedral separability: complexity and polynomial approximation // Machine Learning, 2015. Vol. 101, no 1. P. 231–251. DOI: 10.1007/s10994-015-5505-0
  9. Khachay M. and Poberii M. Complexity and approximability of committee polyhedral separability of sets in general position // Informatica, 2009. Vol. 20, no. 2. P. 217–234.
  10. Khachay M., Pobery M. and Khachay D. Integer partition problem: Theoretical approach to improving accuracy of classifier ensembles // International J. of Artificial Intelligence, 2015. Vol. 13, no. 1. P. 135–146.
  11. Matoušek J. Lectures on Discrete Geometry. Springer: New York, 2002. DOI: 10.1007/978-1-4613-0039-7
  12. Mudgal A. and Pandit S. Covering, hitting, piercing and packing rectangles intersecting an inclined line // Proceedings of the Combinatorial Optimization and Applications: 9th International Conference, (COCOA 2015, Houston, TX, USA, December 18-20, 2015), Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li, and Ding-Zhu Du (Ed.). LNCS, Springer International Publishing: Cham, 2015. Vol. 9486. P. 126–137. DOI: 10.1007/978-3-319-26626-8_10
  13. Ramakrishnan S. and Emary I. M. M. El. Wireless sensor networks: from theory to applications. CRCPress, Taylor & Francis, 2014.
  14. Schapire R. and Freund Y. Boosting: Foundations and algorithms. MIT Press, 2012.
  15. Vapnik V. and Chervonenkis A. On the uniform convergence of relative frequencies of events to their probabilities // Theory Probab. Appl., 1971. Vol.16. P. 264–280. DOI: 10.1137/1116025

DOI: http://dx.doi.org/10.15826/umj.2016.2.010

Article Metrics

Metrics Loading ...


  • There are currently no refbacks.