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

doi:10.46298/dmtcs.2088

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

Institute of Software Technology (7160)

Research output: Contribution to journal › Article › peer-review

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

Original language	English
Pages (from-to)	317-332
Journal	Discrete Mathematics & Theoretical Computer Science
Volume	16
Issue number	3
DOIs	https://doi.org/10.46298/dmtcs.2088
Publication status	Published - 2014

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Access to Document

10.46298/dmtcs.2088

Cite this

@article{fdc21f309b4e4223b1e1a6ced0a8a307,

title = "Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane",

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",

author = "Oswin Aichholzer and Jean Cardinal and Thomas Hackl and Ferran Hurtado and Matias Korman and Alexander Pilz and Rodrigo Silveira and Ryuhei Uehara and Pavel Valtr and Birgit Vogtenhuber and Emo Welzl",

year = "2014",

doi = "10.46298/dmtcs.2088",

language = "English",

volume = "16",

pages = "317--332",

journal = "Discrete Mathematics & Theoretical Computer Science",

issn = "1462-7264",

publisher = "Maison de l'Informatique et des Math{\'e}matiques Discr{\`e}tes",

number = "3",

}

TY - JOUR

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

AU - Aichholzer, Oswin

AU - Cardinal, Jean

AU - Hackl, Thomas

AU - Hurtado, Ferran

AU - Korman, Matias

AU - Pilz, Alexander

AU - Silveira, Rodrigo

AU - Uehara, Ryuhei

AU - Valtr, Pavel

AU - Vogtenhuber, Birgit

AU - Welzl, Emo

PY - 2014

Y1 - 2014

N2 - 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

AB - 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

U2 - 10.46298/dmtcs.2088

DO - 10.46298/dmtcs.2088

M3 - Article

SN - 1462-7264

VL - 16

SP - 317

EP - 332

JO - Discrete Mathematics & Theoretical Computer Science

JF - Discrete Mathematics & Theoretical Computer Science

IS - 3

ER -

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

Abstract

Fields of Expertise

Treatment code (Nähere Zuordnung)

Access to Document

Fingerprint

Cite this