scientific article; zbMATH DE number 1241844
Let \(P\) be a set of \(2n\) points in the plane in general position. A straight line \(H\) passing through two points of \(P\) is called a halving line of \(P\) if each of the two open half-planes bounded by \(H\) contains \(n-1\) points of \(P\). It is shown that \(P\) admits a perfect matching with pairwise crossing line segments if and only if it has precisely \(n\) halving lines. In this case the matching is unique and consists of exactly those segments between two points of \(P\) whose extensions are halving lines. As a consequence, the authors present an \(O(n\log n)\) time, \(O(n)\) space algorithm which decides whether there exists such a matching of \(P\) and, if so, finds it. For the entire collection see [Zbl 0902.00037].
- An improvement of the lower bound on the maximum number of halving lines in planar sets with 32 points
- Perfect matchings with crossings
- A positive fraction mutually avoiding sets theorem
- Partitions of complete geometric graphs into plane trees
- On geometric graphs on point sets in the plane
- Touching perfect matchings and halving lines
- Matching colored points in the plane: Some new results
- Perfect matchings with crossings
- Crossing and intersecting families of geometric graphs on point sets
- Partitioning complete geometric graphs on dense point sets into plane subgraphs
- Partitioning complete geometric graphs on dense point sets into plane subgraphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4225307)
