Skip to Main content Skip to Navigation
Conference papers

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

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-02050539
Contributor : Xavier Goaoc Connect in order to contact the contributor
Submitted on : Thursday, March 7, 2019 - 9:45:21 AM
Last modification on : Tuesday, October 19, 2021 - 11:26:22 AM

Identifiers

`

Citation

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⟩

Share

Metrics

Record views

126

Files downloads

16