Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane

Discrete Mathematics & Theoretical Computer Science, Vol 16, No 3 (2014)

Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane

Oswin Aichholzer, Jean Cardinal, Thomas Hackl, Ferran Hurtado, Matias Korman, Alexander Pilz, Rodrigo Silveira, Ryuhei Uehara, Pavl Valtr, Birgit Vogtenhuber, Emo Welzl

Abstract

We prove that the dual graph of any arrangement of n lines in general position always contains a path of length at least n²/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.

Full Text: PDF PostScript