文章基本信息

标题：An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting
本地全文：下载
作者：Xavier Goaoc ; Andreas Holmsen ; Cyril Nicaud 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：129
页码：1-16
DOI：10.4230/LIPIcs.SoCG.2019.40
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Geometric permutation; Emptiness testing of semi-algebraic sets; Computer-aided proof