Partitioning axis-parallel lines in 3D. (English) Zbl 1535.68422
Summary: Let \(L\) be a set of \(n\) axis-parallel lines in \(\mathbb{R}^3\). We are are interested in partitions of \(\mathbb{R}^3\) by a set \(H\) of three planes such that each open cell in the arrangement \(\mathcal{A}(H)\) is intersected by as few lines from \(L\) as possible. We study such partitions in three settings, depending on the type of splitting planes that we allow. We obtain the following results.
- ●
- There are sets \(L\) of \(n\) axis-parallel lines such that, for any set \(H\) of three splitting planes, there is an open cell in \(\mathcal{A}(H)\) that intersects at least \(\lfloor n/3\rfloor - 1 \approx \frac{1}{3}n\) lines.
- ●
- If we require the splitting planes to be axis-parallel, then there are sets \(L\) of \(n\) axis-parallel lines such that, for any set \(H\) of three splitting planes, there is an open cell in \(\mathcal{A}(H)\) that intersects at least \(\frac{3}{2}\lfloor n/4\rfloor - 1 \approx (\frac{1}{3}+\frac{1}{24}) n\) lines.
Furthermore, for any set \(L\) of \(n\) axis-parallel lines, there exists a set \(H\) of three axis-parallel splitting planes such that each open cell in \(\mathcal{A}(H)\) intersects at most \(\frac{7}{18}n=(\frac{1}{3}+\frac{1}{18})n\) lines. - ●
- For any set \(L\) of \(n\) axis-parallel lines, there exists a set \(H\) of three axis-parallel and mutually orthogonal splitting planes, such that each open cell in \(\mathcal{A}(H)\) intersects at most \(\lceil\frac{5}{12} n \rceil \approx (\frac{1}{3}+\frac{1}{12}) n\) lines.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 51M20 | Polyhedra and polytopes; regular figures, division of spaces |
References:
| [1] | David Avis. Non-partitionable point sets. Information Processing Letters, 19(3):125-129, 1984. · Zbl 0564.51007 |
| [2] | W. A. Beyer and Andrew Zardecki. The early history of the ham sandwich theorem. The American Mathematical Monthly, 111(1):58-61, 2004. doi:10.1080/00029890.2004.11920050. · Zbl 1047.55500 · doi:10.1080/00029890.2004.11920050 |
| [3] | Pavle Blagojević, Florian Frick, Albert Haase, and Günter Ziegler. Topology of the Grünbaum-Hadwiger-Ramos hyperplane mass partition problem. Transactions of the American Mathe-matical Society, 370(10):6795-6824, 2018. · Zbl 1396.52011 |
| [4] | Pavle V. M. Blagojević and Roman Karasev. Partitioning a measure in R 3 . Manuscript, 2016. |
| [5] | Bernard Chazelle. Cuttings. In Handbook of Data Structures and Applications, pages 397-404. Chapman and Hall/CRC, 2018. · Zbl 1387.68249 |
| [6] | Richard Courant and Herbert Robbins. What is mathematics? Bull. Amer. Math. Soc, 48:810-812, 1942. |
| [7] | Branko Grünbaum. Partitions of mass-distributions and of convex bodies by hyperplanes. Pacific Journal of Mathematics, 10(4):1257-1261, 1960. · Zbl 0101.14603 |
| [8] | Larry Guth. Polynomial partitioning for a set of varieties. Math. Proc. Cambridge Philos. Soc., 159(3):459-469, 2015. doi:10.1017/S0305004115000468. · Zbl 1371.14065 · doi:10.1017/S0305004115000468 |
| [9] | H. Hadwiger. Simultane Vierteilung zweier Körper. Arch. Math. (Basel), 17:274-278, 1966. doi:10.1007/BF01899586. · Zbl 0137.41501 · doi:10.1007/BF01899586 |
| [10] | Atsushi Kaneko and M. Kano. Discrete geometry on red and blue points in the plane -a survey -. In Discrete and Computational Geometry: The Goodman-Pollack Festschrift, volume 25 of Algorithms and Combinatorics, pages 551-570. Springer Berlin Heidelberg, 2003. doi:10.1007/978-3-642-55566-4_25. · Zbl 1079.52505 · doi:10.1007/978-3-642-55566-4_25 |
| [11] | Mikio Kano and Jorge Urrutia. Discrete geometry on colored point sets in the plane-a survey. Graphs and Combinatorics, 37:1-53, 2021. doi:10.1007/s00373-020-02210-8. · Zbl 1459.05032 · doi:10.1007/s00373-020-02210-8 |
| [12] | Stefan Langerman and William Steiger. Optimization in arrangements. In STACS 2003, pages 50-61, 2003. doi:10.1007/3-540-36494-3_6. · Zbl 1036.90512 · doi:10.1007/3-540-36494-3_6 |
| [13] | Michael S. Paterson and F. Frances Yao. Optimal binary space partitions for orthogonal objects. J. Algorithms, 13(1):99-113, 1992. doi:10.1016/0196-6774(92)90007-Y. · Zbl 0767.68096 · doi:10.1016/0196-6774(92)90007-Y |
| [14] | Mike Paterson and F. Frances Yao. Efficient binary space partitions for hidden-surface removal and solid modeling. Discret. Comput. Geom., 5:485-503, 1990. doi:10.1007/BF02187806. · Zbl 0701.68042 · doi:10.1007/BF02187806 |
| [15] | Edgardo Roldán-Pensado and Pablo Soberón. A survey of mass partitions. Bulletin of the American Mathematical Society, 2021. |
| [16] | F. Frances Yao, David P. Dobkin, Herbert Edelsbrunner, and Mike Paterson. Partitioning space for range queries. SIAM J. Comput., 18(2):371-384, 1989. doi:10.1137/0218025. · Zbl 0675.68066 · doi:10.1137/0218025 |
| [17] | Rade T Živaljević. Topological methods in discrete geometry. In Handbook of Discrete and Computational Geometry, pages 551-580. Chapman and Hall/CRC, 3rd edition, 2017. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
