2026-07-24T21:21:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10444 2024-03-06T10:46:00Z ddc:004 open_access

An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting Goaoc, Xavier Holmsen, Andreas Nicaud, Cyril Geometric permutation Emptiness testing of semi-algebraic sets Computer-aided proof 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xavier Goaoc and Andreas Holmsen and Cyril Nicaud 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.40 urn:nbn:de:0030-drops-104442 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.40 eng https://creativecommons.org/licenses/by/3.0/legalcode