Cell-paths in mono- and bichromatic line arrangements in the plane
Résumé
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.
Domaines
Mathématique discrète [cs.DM]
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...