An experimental study of forbidden patterns in geometric permutations by combinatorial lifting

Xavier Goaoc (1) , Andreas Holmsen (2) , Cyril Nicaud (3)

1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
2 Department of Mathematical Sciences, KAIST
3 LIGM - Laboratoire d'Informatique Gaspard-Monge

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.

Domaines: Informatique [cs]

Xavier Goaoc, Andreas Holmsen, Cyril Nicaud. An experimental study of forbidden patterns in geometric permutations by combinatorial lifting. 35th International Symposium on Computational Geometry, 2019, Portland, United States. ⟨10.4230/LIPIcs.SoCG.2019.40⟩. ⟨hal-02050539⟩