I allmänhet finns det ingen känd total polynomalgoritm för antingen konvexa skrov eller vertex-räkning, dvs. En algoritm vars komplexitet beror polynomiskt på ingångs- och utgångsstorlekarna. Det är därför viktigt att identifiera problem (och polytop representationer) för vilka total polynom-tid algoritmer kan erhållas. Vi erbjuder den första totala polynom-tid algoritm för att beräkna kantskelett (inklusive vertex räkning) av en polytop som ges av en optimering eller separation orakel, där vi också ges en superuppsättning av dess kant riktningar. Vi erbjuder också en rumseffektiv variant av vår algoritm genom att använda omvänd sökning. Alla komplexa gränser hänvisar till (orakel) Turing maskin modell. Det finns ett antal polytop klasser naturligt definieras av orakel; för vissa av dem varken vertex eller facet representation är uppenbart. Vi överväger två huvudsakliga tillämpningar, där vi får (svagt) totala polynom-tid algoritmer: Signed Minkowski summor av konvexa polytoper, där polytoper kan subtraheras under förutsättning att den undertecknade summan är en konvex polytop, och beräkning av sekundära, resulterande, och diskriminerande polytoper. Ytterligare applikationer inkluderar convex combinatorial optimering och konvex heltal programmering, där vi erbjuder ett nytt tillvägagångssätt, vilket eliminerar komplexitetens exponentiella beroende i dimensionen.
I REF presenteras en polynom-tidsalgoritm för att beräkna kantskelettet hos en polytop.
Efficient edge-skeleton computation for polytopes defined by oracles
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}