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

Institut für Softwaretechnologie (7160)

Publikation: Beitrag in einer Fachzeitschrift › Artikel › Begutachtung

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

Originalsprache	englisch
Seiten (von - bis)	317-332
Fachzeitschrift	Discrete Mathematics & Theoretical Computer Science
Jahrgang	16
Ausgabenummer	3
DOIs	https://doi.org/10.46298/dmtcs.2088
Publikationsstatus	Veröffentlicht - 2014

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Zugriff auf Dokument

10.46298/dmtcs.2088

Dieses zitieren

@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)

Zugriff auf Dokument

Fingerprint

Dieses zitieren