Flip Distance to some Plane Configurations

Authors Ahmad Biniaz, Anil Maheshwari, Michiel Smid



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.11.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Author Details

Ahmad Biniaz
  • Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada
Anil Maheshwari
  • School of Computer Science, Carleton University, Ottawa, Canada
Michiel Smid
  • School of Computer Science, Carleton University, Ottawa, Canada

Cite AsGet BibTex

Ahmad Biniaz, Anil Maheshwari, and Michiel Smid. Flip Distance to some Plane Configurations. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SWAT.2018.11

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(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/2-1 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 n-2 for points in convex position, and f(M')= 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(n log n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Discrete mathematics
Keywords
  • flip distance
  • non-crossing edges
  • perfect matchings
  • spanning trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Oswin Aichholzer, Andrei Asinowski, and Tillmann Miltzow. Disjoint compatibility graph of non-crossing matchings of points in convex position. Electr. J. Comb., 22(1):P1.65, 2015. Google Scholar
  2. Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García Olaverri, Clemens Huemer, Ferran Hurtado, Mikio Kano, Alberto Márquez, David Rappaport, Shakhar Smorodinsky, Diane L. Souvaine, Jorge Urrutia, and David R. Wood. Compatible geometric matchings. Comput. Geom., 42(6-7):617-626, 2009. Google Scholar
  3. Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz. Flip distance between triangulations of a simple polygon is NP-complete. Discrete & Computational Geometry, 54(2):368-389, 2015. Google Scholar
  4. Greg Aloupis, Luis Barba, Stefan Langerman, and Diane L. Souvaine. Bichromatic compatible matchings. Comput. Geom., 48(8):622-633, 2015. Google Scholar
  5. Greg Aloupis, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara, and Perouz Taslakian. Non-crossing matchings of points with geometric objects. Computational Geometry: theory and Applications, 46(1):78-92, 2013. Google Scholar
  6. Ahmad Biniaz, Anil Maheshwari, and Michiel Smid. Bottleneck bichromatic plane matching of points. In Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG), pages 431-435, 2014. Google Scholar
  7. Édouard Bonnet and Tillmann Miltzow. Flip distance to a non-crossing perfect matching. EuroCG, 2016. Google Scholar
  8. Prosenjit Bose and Ferran Hurtado. Flips in planar graphs. Comput. Geom., 42(1):60-80, 2009. Google Scholar
  9. Prosenjit Bose and Sander Verdonschot. A history of flips in combinatorial triangulations. In XIV Spanish Meeting on Computational Geometry (EGC), pages 29-44, 2011. Google Scholar
  10. John Gunnar Carlsson, Benjamin Armbruster, Saladi Rahul, and Haritha Bellam. A bottleneck matching problem with edge-crossing constraints. International Journal of Computational Geometry and Applcations, 25(4):245-262, 2015. Google Scholar
  11. Kenneth L. Clarkson. Nearest neighbor queries in metric spaces. Discrete & Computational Geometry, 22(1):63-93, 1999. Google Scholar
  12. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, chapter 21: Data structures for Disjoint Sets. The MIT Press and McGraw-Hill Book Company, second edition, 2001. Google Scholar
  13. Herbert Edelsbrunner, Pavel Valtr, and Emo Welzl. Cutting dense point sets in half. Discrete & Computational Geometry, 17(3):243-255, 1997. Google Scholar
  14. Ferran Hurtado, Marc Noy, and Jorge Urrutia. Flipping edges in triangulations. Discrete & Computational Geometry, 22(3):333-346, 1999. Google Scholar
  15. Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth. Disjoint compatible geometric matchings. Discrete & Computational Geometry, 49(1):89-131, 2013. Google Scholar
  16. Charles L Lawson. Transforming triangulations. Discrete Mathematics, 3(4):365-372, 1972. Google Scholar
  17. Yoshiaki Oda and Mamoru Watanabe. The number of flips required to obtain non-crossing convex cycles. In Proceedings of the International Conference on Computational Geometry and Graph Theory (KyotoCGGT), pages 155-165, 2007. Google Scholar
  18. Alfredo García Olaverri, Clemens Huemer, Ferran Hurtado, and Javier Tejel. Compatible spanning trees. Comput. Geom., 47(5):563-584, 2014. Google Scholar
  19. Pavel Valtr. Planar point sets with bounded ratios of distances. PhD thesis, Fachbereich Mathematik, Freie Universität Berlin, 1994. Google Scholar
  20. Pavel Valtr. Lines, line-point incidences and crossing families in dense sets. Combinatorica, 16(2):269-294, 1996. Google Scholar
  21. Jan van Leeuwen and Anneke A. Schoone. Untangling a travelling salesman tour in the plane. In Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG), pages 87-98, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail