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, Pavel Valtr, Birgit Vogtenhuber, Emo Welzl

Research output: Contribution to journalArticlepeer-review


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
Original languageEnglish
Pages (from-to)317-332
JournalDiscrete Mathematics & Theoretical Computer Science
Issue number3
Publication statusPublished - 2014

Fields of Expertise

  • Information, Communication & Computing

Treatment code (Nähere Zuordnung)

  • Basic - Fundamental (Grundlagenforschung)

Cite this