@article{Aronov_Basit_de Berg_Gudmundsson_2023, title={Partitioning Axis-Parallel Lines in 3D}, volume={2}, url={https://cgt-journal.org/index.php/cgt/article/view/14}, DOI={10.57717/cgt.v2i1.14}, abstractNote={<p>Let L be a set of n axis-parallel lines in R<sup>3</sup>. We are are interested in partitions of R<sup>3</sup> by a set H of three planes such that each open cell in the arrangement 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.<br />* 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 A(H) that intersects at least ⌊n/3⌋ - 1 ≈ n/3 lines.<br />* 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 A(H) that intersects at least (3/2) ⌊n/3⌋ - 1 ≈ (1/3 + 1/24) n lines.<br />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 A(H) intersects at most (7/18) n = (1/3 + 1/18) n lines.<br />* 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 A(H) intersects at most ⌈5/12 n⌉ ≈ (1/3 + 1/12) n lines.</p>}, number={1}, journal={Computing in Geometry and Topology}, author={Aronov, Boris and Basit, Abdul and de Berg, Mark and Gudmundsson, Joachim}, year={2023}, month={Dec.}, pages={9:1–9:20} }