En zonotope är Minkowski tillägg av linjesegment i R d. Den zonotope byggproblem är att lista alla extrema punkter i en zonotope ges av sina linjesegment. Genom dualitet är det likvärdigt med det konstruktionsproblem som är att generera alla regioner av ett arrangemang av hyperplane. Genom att ersätta linjesegment med konvexa V-polytoper får vi en naturlig generalisering av zonotope-konstruktionsproblemet: konstruktionen av Minkowski-tillägget av k-polytoper. Gritzmann och Sturmfels studerade detta allmänna problem i olika aspekter och presenterade polynomalgoritmer för problemet när en av parametrarna k eller d är fast. Huvudsyftet med detta arbete är att införa en effektiv algoritm för variabel d och k. Här kallar vi en algoritm effektiv eller polynomial om den körs i tid avgränsad av en polynom funktion av både indatastorlek och utdatastorlek. Algoritmen är en naturlig förlängning av en känd algoritm för zonotope konstruktion, baserad på linjär programmering och omvänd sökning. Den är kompakt, mycket parallelliserbar och mycket lätt att genomföra. Detta arbete har motiverats av användningen av polyhedral beräkning för optimal toleransbestämning inom maskinteknik.
Komei Fukuda REF föreslog en polynomalgoritm för att räkna upp alla hörn av Minkowski summan av k V-polytoper.
From the zonotope construction to the Minkowski addition of convex polytopes
{'venue': 'Journal of Symbolic Computation', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}