Biniaz, Ahmad ;
Maheshwari, Anil ;
Smid, Michiel
Flip Distance to some Plane Configurations
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 noncrossing perfect matching by a finite sequence of flip operations. The flip operation removes two crossing edges from M and adds two noncrossing 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(n Delta) 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 for point sets with sublinear spread. For a matching M on n points in convex position we prove that f(M)=n/21 and F(M)={{n/2} choose 2}; these bounds are tight.
Any bound on F(*) carries over to the bichromatic setting, while this is not necessarily true for f(*). Let M' be a bichromatic matching. The best known upper bound for f(M') is the same as for F(M'), which is essentially O(n^3). We prove that f(M')<=slant n2 for points in convex position, and f(M')= O(n^2) for semicollinear 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(n log n).
BibTeX  Entry
@InProceedings{biniaz_et_al:LIPIcs:2018:8837,
author = {Ahmad Biniaz and Anil Maheshwari and Michiel Smid},
title = {{Flip Distance to some Plane Configurations}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {11:111:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8837},
URN = {urn:nbn:de:0030drops88371},
doi = {10.4230/LIPIcs.SWAT.2018.11},
annote = {Keywords: flip distance, noncrossing edges, perfect matchings, spanning trees}
}
04.06.2018
Keywords: 

flip distance, noncrossing edges, perfect matchings, spanning trees 
Seminar: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Issue date: 

2018 
Date of publication: 

04.06.2018 