Partitioning Axis-Parallel Lines in 3D

Authors

• Boris Aronov New York University
• Abdul Basit Monash University
• Mark de Berg TU Eindhoven
• Joachim Gudmundsson University of Sydney

Abstract

Let L be a set of n axis-parallel lines in R3. We are are interested in partitions of R3 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.
* 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.
* 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.
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.
* 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.

2023-12-17

How to Cite

Aronov, B., Basit, A., de Berg, M., & Gudmundsson, J. (2023). Partitioning Axis-Parallel Lines in 3D. Computing in Geometry and Topology, 2(1), 9:1–9:20. https://doi.org/10.57717/cgt.v2i1.14

Section

Original Research Articles