Bisecting three classes of lines
Alexander Pilz, Patrick Schnider · Computational Geometry · 2021
We consider the following problem: Let L be an arrangement of n lines in R3 in general position colored red, green, and blue. Does there exist a vertical plane P such that a line in P simultaneously bisects all three classes of points induced by the intersection of lines in L with P? Recently, Schnider used topological methods to prove that such a cross-section always exists. In this work, we give an alternative proof of this fact, using only methods from discrete geometry. With this combinatorial proof at hand, we devise an O(n2log2(n)) time algorithm to find such a plane and a bisector of the induced cross-section. We do this by providing a general framework, from which we expect that it can be applied to solve similar problems on cross-sections and kinetic points.