Cell-paths in mono- and bichromatic line arrangements in the plane
Oswin Aichholzer, Jean Cardinal, Thomas Hackl, Ferrán Hurtado, Matias Korman, Alexander Pilz, Rodrigo I. Silveira, Ryuhei Uehara, Pável Valtr, Birgit Vogtenhuber, Emo Welzl · Discrete Mathematics & Theoretical Computer Science · 2014
Combinatorics We prove that the dual graph of any arrangement of n lines in general position always contains a path of length at least n2/4. Further, we show that in every arrangement of n red and blue lines — in general position and not all of the same color — there is a simple path through at least n cells where red and blue lines are crossed alternatingly.