Cell-paths in mono- and bichromatic line arrangements in the plane
Oswin Aichholzer (1), Jean Cardinal (2) (3), Thomas Hackl (1), Ferran Hurtado (4) (5) (6), Matias Korman (7) (8) (9) (10), Alexander Pilz (1), Rodrigo I. Silveira (4) (11) (5) (6), Ryuhei Uehara (12), Pavel Valtr (13) (14) (15), Birgit Vogtenhuber (1), Emo Welzl (16)
(1) Graz University of Technology [Graz]
(2) Université libre de Bruxelles
(3) Université libre de Bruxelles = Free University of Brussels
(4) Universitat Politècnica de Catalunya [Barcelona]
(5) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona]
(6) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne = Polytechnic University of Catalunya [Barcelona]
(7) National Institute of Informatics
(8) Japan Science and Technology Agency
(9) IRATO / Kawarabayashi Large Graph Project [Japan]
(10) IRATO / Kawarabayashi Large Graph Project
(11) Centro de Investigaçao e Desenvolvimento em Matematica e Aplicaçoes
(12) Japan Advanced Institute of Science and Technology
(13) Charles University [Prague]
(14) Univerzita Karlova [Praha, Česká republika] = Charles University [Prague, Czech Republic]
(15) Univerzita Karlova [Praha, Česká republika] = Charles University [Prague, Czech Republic] = Université Charles [Prague, Republique tchèque]
(16) Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]
Abstract
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.
