Flip distance to some plane configurations

DOI10.1016/J.COMGEO.2019.01.008MaRDI QIDQ2331207zbMATH OpenOpenAlexWikidataFDO

Authors Ahmad Biniaz, Anil Maheshwari, Michiel Smid

Publication date 25 October 2019

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.00791, https://drops.dagstuhl.de/opus/volltexte/2018/8837/

zbMATH Keywords

flip distancenon-crossing edgesperfect matchingsspanning trees

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We study an old geometric optimization problem in the plane. Given a perfect matching $M$ on a set of $n$ points in the plane, we can transform it to a non-crossing perfect matching by a finite sequence of flip operations. The flip operation removes two crossing edges from $M$ and adds two non-crossing edges. Let $f(M)$ and $F(M)$ denote the minimum and maximum lengths of a flip sequence on $M$, respectively. It has been proved by Bonnet and Miltzow (2016) that $f(M)=O(n^2)$ and by van Leeuwen and Schoone (1980) that $F(M)=O(n^3)$. We prove that $f(M)=O(nDelta)$ where $Delta$ is the spread of the point set, which is defined as the ratio between the longest and the shortest pairwise distances. This improves the previous bound if the point set has sublinear spread. For a matching $M$ on $n$ points in convex position we prove that $f(M)=n/2-1$ and $F(M)=n/2choose2$; these bounds are tight. Any bound on $F(cdot)$ carries over to the bichromatic setting, while this is not necessarily true for $f(cdot)$. Let $M^{\prime }$ be a bichromatic matching. The best known upper bound for $f(M^{\prime })$ is the same as for $F(M^{\prime })$, which is essentially $O(n^3)$. We prove that $f(M^{\prime })len-2$ for points in convex position, and $f(M^{\prime })=O(n^2)$ for semi-collinear points. The flip operation can also be defined on spanning trees. For a spanning tree $T$ on a convex point set we show that $f(T)=O(nlogn)$.

Recommendations

• Flip distance to some plane configurations
• On flips in planar matchings
• Flip distance is in FPT time O(n+ k c^k)

Cites work

• A bottleneck matching problem with edge-crossing constraints
• A history of flips in combinatorial triangulations
• Bichromatic compatible matchings
• Compatible geometric matchings
• Compatible spanning trees
• Cutting dense point sets in half
• Disjoint compatibility graph of non-crossing matchings of points in convex position
• Disjoint compatible geometric matchings
• Flipping edges in triangulations
• Flips in planar graphs
• scientific article; zbMATH DE number 3882232 (Why is no real title available?)
• scientific article; zbMATH DE number 835734 (Why is no real title available?)
• Lines, line-point incidences and crossing families in dense sets
• Nearest neighbor queries in metric spaces
• Non-crossing matchings of points with geometric objects
• The Number of Flips Required to Obtain Non-crossing Convex Cycles
• Transforming triangulations

Cited in

(10)

• Bounded-angle minimum spanning trees
• Flip distance to some plane configurations
• On flips in planar matchings
• On the longest flip sequence to untangle segments in the plane
• A note on the flip distance between non-crossing spanning trees
• Approximation ineffectiveness of a tour-untangling heuristic
• Short flip sequences to untangle segments in the plane
• Reconfiguration of non-crossing spanning trees
• Performance of efficient variants of the 2-opt heuristic for the traveling salesperson problem
• Flips in odd matchings

This page was built for publication: Flip distance to some plane configurations

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