Bichromatic Perfect Matchings with Crossings

Oswin Aichholzer; Stefan Felsner; Rosna Paul; Manfred Scheucher; Birgit Vogtenhuber

Bichromatic Perfect Matchings with Crossings

Oswin Aichholzer, Stefan Felsner, Rosna Paul, Manfred Scheucher, Birgit Vogtenhuber

Institute of Software Technology (7160)

Research output: Working paper › Preprint

Abstract

We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least 3n²/8 - n/2 + c crossings, for some -1/2 ≤ c ≤ 1/8. This bound is tight since for any k > 3n^2/8 − n/2 + 1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n²/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n²/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.≤bound is tight since for any k>3n²/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n²/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.

Original language	Undefined/Unknown
Publisher	arXiv
Publication status	Published - 1 Sept 2023

Keywords

cs.CG
math.CO

Access to Document

2309.00546v1

Cite this

@techreport{bacb261b5636445c9711042a5d7ecc15,

title = "Bichromatic Perfect Matchings with Crossings",

abstract = "We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least 3n2/8 - n/2 + c crossings, for some -1/2 ≤ c ≤ 1/8. This bound is tight since for any k > 3n2/8 − n/2 + 1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.≤bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.",

keywords = "cs.CG, math.CO",

author = "Oswin Aichholzer and Stefan Felsner and Rosna Paul and Manfred Scheucher and Birgit Vogtenhuber",

note = "Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)",

year = "2023",

month = sep,

day = "1",

language = "undefiniert/unbekannt",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Bichromatic Perfect Matchings with Crossings

AU - Aichholzer, Oswin

AU - Felsner, Stefan

AU - Paul, Rosna

AU - Scheucher, Manfred

AU - Vogtenhuber, Birgit

N1 - Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

PY - 2023/9/1

Y1 - 2023/9/1

N2 - We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least 3n2/8 - n/2 + c crossings, for some -1/2 ≤ c ≤ 1/8. This bound is tight since for any k > 3n2/8 − n/2 + 1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.≤bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.

AB - We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least 3n2/8 - n/2 + c crossings, for some -1/2 ≤ c ≤ 1/8. This bound is tight since for any k > 3n2/8 − n/2 + 1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.≤bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.bound is tight since for any k>3n2/n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.

KW - cs.CG

KW - math.CO

M3 - Preprint

BT - Bichromatic Perfect Matchings with Crossings

PB - arXiv

ER -