Linear transformation distance for bichromatic matchings

DOI10.1016/J.COMGEO.2017.05.003zbMATH Open1380.05050arXiv1312.0884OpenAlexW2612435103MaRDI QIDQ1699281FDOQ1699281

Authors: Oswin Aichholzer, Luis Barba, T. Hackl, Alexander Pilz, Birgit Vogtenhuber 

Publication date: 19 February 2018

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: Let $P=BcupR$ be a set of $2n$ points in general position, where $B$ is a set of $n$ blue points and $R$ a set of $n$ red points. A emph{$BR$-matching} is a plane geometric perfect matching on $P$ such that each edge has one red endpoint and one blue endpoint. Two $BR$-matchings are compatible if their union is also plane. The emph{transformation graph of $BR$-matchings} contains one node for each $BR$-matching and an edge joining two such nodes if and only if the corresponding two $BR$-matchings are compatible. In SoCG 2013 it has been shown by Aloupis, Barba, Langerman, and Souvaine that this transformation graph is always connected, but its diameter remained an open question. In this paper we provide an alternative proof for the connectivity of the transformation graph and prove an upper bound of $2n$ for its diameter, which is asymptotically tight.

Full work available at URL: https://arxiv.org/abs/1312.0884

Recommendations

• Linear transformation distance for bichromatic matchings
• Bichromatic compatible matchings
• Bichromatic compatible matchings
• Structural properties of bichromatic non-crossing matchings
• Monochromatic plane matchings in bicolored point set

zbMATH Keywords

perfect matchingsreconfiguration problembichromatic point settransformation graphcompatible matchings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms for ham-sandwich cuts
• Ray shooting in polygons using geodesic triangulations
• Problem-solving through problems
• Encompassing colored planar straight line graphs
• Compatible geometric matchings
• Shooting permanent rays among disjoint polygons in the plane
• Disjoint compatible geometric matchings
• Vertex-colored encompassing graphs
• Bichromatic compatible matchings
• Quasi-parallel segments and characterization of unique bichromatic matchings
• Linear transformation distance for bichromatic matchings

Cited In (9)

• Bichromatic compatible matchings
• On compatible matchings
• Structural properties of bichromatic non-crossing matchings
• On Compatible Matchings
• Plane augmentation of plane graphs to meet parity constraints
• Bichromatic compatible matchings
• Compatible spanning trees in simple drawings of \(K_n\)
• Discrete geometry on colored point sets in the plane -- a survey
• Linear transformation distance for bichromatic matchings

This page was built for publication: Linear transformation distance for bichromatic matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699281)