On a matching problem in the plane

DOI10.1016/S0012-365X(99)00201-0MaRDI QIDQ1969786zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, William Steiger

Publication date 22 January 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00201-0

computational geometry matching planar arrangements

Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

We are given a finite set \(S\) of \(n = w + b\) points in the plane, where \(w\) of them are white and \(b\) of them are black. The points of \(S\) are assumed to be in general position, i.e. no three of them are on a line. The task is to find a matching \(F(S)\) that only matches points of the same color, that has no crossings between the line segments that join matched points, and which leaves the smallest number of points of \(S\) unmatched. In other words, we would like to minimize the number of independent points in \(S\). In the case where \(w\) and \(b\) (and therefore also \(n\)) are even a lower bound of \(\frac{5}{6}\) and an upper bound of \(\frac{155}{156}\) for the minimal number of independent points in \(S\) is derived. Also some results are given for the case with no restriction on the parity of \(n\), \(w\) and \(b\). These results include some special cases and a relation between the parity restricted bound and the general case. Also the generalization of this problem to a fixed number of colors, where each color set contains an even number of points and only points of the same color are to be matched with non-intersecting segments is briefly discussed.

Recommendations

Cited in

(21)

This page was built for publication: On a matching problem in the plane

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