Document Open Access Logo

An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting

Authors Xavier Goaoc, Andreas Holmsen, Cyril Nicaud

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.40.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Xavier Goaoc
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Andreas Holmsen
  • Department of Mathematical Sciences, KAIST, Daejeon, South Korea
Cyril Nicaud
  • Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE, UPEM, F-77454, Marne-la-Vallée, France

Funding

  • Goaoc, Xavier: Supported by Institut Universitaire de France.
  • Holmsen, Andreas: Supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2016R1D1A1B03930998).

Cite AsGet BibTex

Xavier Goaoc, Andreas Holmsen, and Cyril Nicaud. An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.40

Abstract

We study the problem of deciding if a given triple of permutations can be realized as geometric permutations of disjoint convex sets in R^3. We show that this question, which is equivalent to deciding the emptiness of certain semi-algebraic sets bounded by cubic polynomials, can be "lifted" to a purely combinatorial problem. We propose an effective algorithm for that problem, and use it to gain new insights into the structure of geometric permutations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Computing methodologies → Combinatorial algorithms
Keywords
  • Geometric permutation
  • Emptiness testing of semi-algebraic sets
  • Computer-aided proof

Metrics

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

Related Versions

References

  1. B Aronov and S. Smorodinsky. On geometric permutations induced by lines transversal through a fixed point. Discrete &Computational Geometry, 34:285-294, 2005. Google Scholar
  2. Andrei Asinowski and Meir Katchalski. Forbidden Families of Geometric Permutations in ℝ^d. Discrete & Computational Geometry, 34(1):1-10, 2005. URL: http://dx.doi.org/10.1007/s00454-004-1110-x.
  3. O. Cheong, X. Goaoc, and H.-S. Na. Geometric permutations of disjoint unit spheres. Computational Geometry: Theory &Applications, 30:253-270, 2005. Google Scholar
  4. Felipe Cucker, Peter Bürgisser, and Pierre Lairez. Computing the homology of basic semialgebraic sets in weak exponential time. arXiv preprint, 2017. URL: http://arxiv.org/abs/1706.07473.
  5. James H Davenport and Joos Heintz. Real quantifier elimination is doubly exponential. Journal of Symbolic Computation, 5(1-2):29-35, 1988. Google Scholar
  6. Herbert Edelsbrunner and Micha Sharir. The maximum number of ways to stab n convex non-intersecting sets in the plane is 2n-2. Discrete &Computational Geometry, 5:35-42, 1990. Google Scholar
  7. B. Grünbaum. On common transversals. Archiv der Mathematik, 9:465-469, 1958. Google Scholar
  8. Philippe Guigue and Olivier Devillers. Fast and robust triangle-triangle overlap test using orientation predicates. Journal of graphics tools, 8(1):25-32, 2003. Google Scholar
  9. Jae-Soon Ha, Otfried Cheong, Xavier Goaoc, and Jungwoo Yang. Geometric permutations of non-overlapping unit balls revisited. Computational Geometry, 53:36-50, 2016. Google Scholar
  10. Andreas Holmsen and Rephael Wenger. Helly-type Theorems and geometric transversals. Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl, pages 63-82, 2017. Google Scholar
  11. Erich Kaltofen, Bin Li, Zhengfeng Yang, and Lihong Zhi. Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients. J. Symb. Comput., 47(1):1-15, 2012. Google Scholar
  12. M Katchalski. A conjecture of Grünbaum on common transversals. Math. Scand., 59:192-198, 1986. Google Scholar
  13. M. Katchalski, T. Lewis, and J. Zaks. Geometric permutations for convex sets. Discrete Math., 54:271-284, 1985. Google Scholar
  14. M Katchalski, Ted Lewis, and A Liu. Geometric permutations and common transversals. Discrete &Computational Geometry, 1(4):371-377, 1986. Google Scholar
  15. Jan Kratochvíl and Jirí Matousek. Intersection graphs of segments. J. Comb. Theory, Ser. B, 62(2):289-315, 1994. Google Scholar
  16. Henri Lombardi, Daniel Perrucci, and Marie-Françoise Roy. An elementary recursive bound for effective Positivstellensatz and Hilbert 17-th problem. arXiv preprint, 2014. URL: http://arxiv.org/abs/1404.2338.
  17. A. Marcus and G. Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107:153-160, 2004. Google Scholar
  18. János Pach and Micha Sharir. Combinatorial geometry and its algorithmic applications: The Alcalá lectures. 152. American Mathematical Soc., 2009. Google Scholar
  19. James Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. Journal of symbolic computation, 13(3):255-299, 1992. Google Scholar
  20. Natan Rubin, Haim Kaplan, and Micha Sharir. Improved bounds for geometric permutations. SIAM Journal on Computing, 41(2):367-390, 2012. Google Scholar
  21. Marcus Schaefer and Daniel Štefankovič. Fixed points, Nash equilibria, and the existential theory of the reals. Theory of Computing Systems, 60(2):172-193, 2017. Google Scholar
  22. S. Smorodinsky, J.S.B Mitchell, and M. Sharir. Sharp bounds on geometric permutations for pairwise disjoint balls in ℝ^d. Discrete &Computational Geometry, 23:247-259, 2000. Google Scholar
  23. Csaba D Toth, Joseph O'Rourke, and Jacob E Goodman. Handbook of discrete and computational geometry. Chapman and Hall/CRC, 2017. Google Scholar
  24. H. Tverberg. Proof of Grünbaum’s conjecture on common transversals for translates. Discrete &Computational Geometry, 4:191-203, 1989. Google Scholar
  25. Helge Tverberg. On geometric permutations and the Katchalski-Lewis conjecture on partial transversals for translates. DIMACS Ser. Discrete Math. Theor. Comp. Sci., 6:351-361, 1991. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact