An $ O(\nu\log\nu) $ upper bound for piercing discrete axis-parallel rectangles

Wei Rao; Wei Rao

doi:10.3934/math.20261158

AIMS Mathematics

2026, Volume 11, Issue 9: 29135-29144. doi: 10.3934/math.20261158

Previous Article Next Article

Research article Special Issues

An $ O(\nu\log\nu) $ upper bound for piercing discrete axis-parallel rectangles

Wei Rao ^,

Laboratory of Discrete and Combinatorial Optimization, Moscow Institute of Physics and Technology, Dolgoprudny 141700, Russia

Received: 05 July 2026 Revised: 16 August 2026 Accepted: 24 August 2026 Published: 10 September 2026
MSC : 05C10, 05C65, 05D15, 52A35, 52C15

Let $ P\subset\mathbb R^2 $ be a finite set, and let $ \mathcal R $ be a nonempty finite family of axis-parallel rectangles, each containing at least one point of $ P $. We study the relation between the piercing number $ \tau = \tau(\mathcal R|_P) $ and the matching number $ \nu = \nu(\mathcal R|_P) $ of the trace family $ \mathcal R|_P = \{R\cap P:R\in\mathcal R\} $. We prove that $ \tau\le 24\nu\log_2(2\nu) = O(\nu\log\nu) $, improving the previously known upper bound $ O((\nu\log\log\nu)^2) $.
- discrete axis-parallel rectangles,
- piercing number,
- matching number,
- $ (p, q) $-property,
- geometric transversals,
- outerplanar graphs,
- treewidth
Citation: Wei Rao. An $ O(\nu\log\nu) $ upper bound for piercing discrete axis-parallel rectangles[J]. AIMS Mathematics, 2026, 11(9): 29135-29144. doi: 10.3934/math.20261158

Related Papers:

Abstract

Let $ P\subset\mathbb R^2 $ be a finite set, and let $ \mathcal R $ be a nonempty finite family of axis-parallel rectangles, each containing at least one point of $ P $. We study the relation between the piercing number $ \tau = \tau(\mathcal R|_P) $ and the matching number $ \nu = \nu(\mathcal R|_P) $ of the trace family $ \mathcal R|_P = \{R\cap P:R\in\mathcal R\} $. We prove that $ \tau\le 24\nu\log_2(2\nu) = O(\nu\log\nu) $, improving the previously known upper bound $ O((\nu\log\log\nu)^2) $.

References

[1]	A. Holmsen, R. Wenger, Helly-type theorems and geometric transversals, In: J. E. Goodman, J. O'Rourke, C. D. Tóth, Handbook of discrete and computational geometry, 3 Eds., CRC Press, 2017, 91–123.
[2]	N. Amenta, J. A. De Loera, P. Soberón, Helly's theorem: new variations and applications, In: H. A. Harrington, M. Omar, M. Wright, Algebraic and geometric methods in discrete mathematics, American Mathematical Society, 2017, 55–95. https://doi.org/10.1090/conm/685/13718
[3]	J. A. De Loera, X. Goaoc, F. Meunier, N. H. Mustafa, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Bull. Amer. Math. Soc., 56 (2019), 415–511. https://doi.org/10.1090/bull/1653 doi: 10.1090/bull/1653
[4]	H. Hadwiger, H. Debrunner, Über eine Variante zum Hellyschen Satz, Arch. Math., 8 (1957), 309–313. https://doi.org/10.1007/BF01898794 doi: 10.1007/BF01898794
[5]	N. Alon, D. J. Kleitman, Piercing convex sets and the Hadwiger-Debrunner $(p, q)$-problem, Adv. Math., 96 (1992), 103–112. https://doi.org/10.1016/0001-8708(92)90052-M doi: 10.1016/0001-8708(92)90052-M
[6]	C. Keller, S. Smorodinsky, A new lower bound on Hadwiger-Debrunner numbers in the plane, Isr. J. Math., 244 (2021), 649–680. https://doi.org/10.1007/s11856-021-2185-2 doi: 10.1007/s11856-021-2185-2
[7]	I. Tomon, Lower bounds for piercing and coloring boxes, Adv. Math., 435 (2023), 109360. https://doi.org/10.1016/j.aim.2023.109360 doi: 10.1016/j.aim.2023.109360
[8]	J. R. Correa, L. Feuilloley, P. Pérez-Lantero, J. A. Soto, Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity, Discrete Comput. Geom., 53 (2015), 344–365. https://doi.org/10.1007/s00454-014-9661-y doi: 10.1007/s00454-014-9661-y
[9]	D. Ajwani, R. Gajjala, R. Raman, S. Ray, A counterexample to Wegner's conjecture for axis-parallel rectangles, arXiv, 2026. https://doi.org/10.48550/arXiv.2606.17854
[10]	N. Halman, Discrete and lexicographic Helly-type theorems, Discrete Comput. Geom., 39 (2008), 690–719. https://doi.org/10.1007/s00454-007-9028-8 doi: 10.1007/s00454-007-9028-8
[11]	T. Edwards, P. Soberón, Extensions of discrete Helly theorems for boxes, SIAM J. Discrete Math., 39 (2025), 1349–1362. https://doi.org/10.1137/24M1658358 doi: 10.1137/24M1658358
[12]	T. Eom, M. Kim, E. Lee, Fractional discrete Helly for pairs in a family of boxes, arXiv, 2025. https://doi.org/10.48550/arXiv.2503.11997
[13]	N. Frankl, A. Jung, Helly-type theorems for monotone properties of boxes, arXiv, 2025. https://doi.org/10.48550/arXiv.2503.22571
[14]	R. Gangopadhyay, A. Polyanskii, W. Rao, New Helly-type results for discrete boxes: quantitative colorful and $(p, q)$-variants, arXiv, 2025. https://doi.org/10.48550/arXiv.2509.13115
[15]	W. Rao, A note on piercing discrete rectangles, arXiv, 2026. https://doi.org/10.48550/arXiv.2604.04024
[16]	N. Alon, Covering a hypergraph of subgraphs, Discrete Math., 257 (2002), 249–254. https://doi.org/10.1016/S0012-365X(02)00427-2 doi: 10.1016/S0012-365X(02)00427-2
[17]	F. Gurski, R. Weishaupt, The behavior of tree-width and path-width under graph operations and graph transformations, Algorithms, 18 (2025), 386. https://doi.org/10.3390/a18070386 doi: 10.3390/a18070386

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)