Hamiltonian Meander Paths and Cycles on Bichromatic Point Sets

EasyChair Preprint 3130

Abstract

We show that any set of n blue and n red points on a line admits a plane meander path, that is, a crossing-free spanning path that crosses the line on red and blue points in alternation. For meander cycles, we derive tight bounds on the minimum number of necessary crossings which depend on the coloring of the points. Finally, we provide some relations for the number of plane meander paths.

Keyphrases: bichromatic point set, meander cycles, meander paths

@booklet{EasyChair:3130,
  author    = {Oswin Aichholzer and Carlos Alegrı́a and Irene Parada and Alexander Pilz and Javier Tejel and Csaba D. Tóth and Jorge Urrutia and Birgit Vogtenhuber},
  title     = {Hamiltonian Meander Paths and Cycles on Bichromatic Point Sets},
  howpublished = {EasyChair Preprint 3130},
  year      = {EasyChair, 2020}}