×

zbMATH — the first resource for mathematics

Efficient edge-skeleton computation for polytopes defined by oracles. (English) Zbl 1336.68262
Summary: In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e., an algorithm whose complexity depends polynomially on the input and output sizes. It is thus important to identify problems and polytope representations for which total polynomial-time algorithms can be obtained. We offer the first total polynomial-time algorithm for computing the edge-skeleton – including vertex enumeration – of a polytope given by an optimization or separation oracle, where we are also given a superset of its edge directions. We also offer a space-efficient variant of our algorithm by employing reverse search. All complexity bounds refer to the (oracle) Turing machine model. There is a number of polytope classes naturally defined by oracles; for some of them neither vertex nor facet representation is obvious. We consider two main applications, where we obtain (weakly) total polynomial-time algorithms: Signed Minkowski sums of convex polytopes, where polytopes can be subtracted provided the signed sum is a convex polytope, and computation of secondary, resultant, and discriminant polytopes. Further applications include convex combinatorial optimization and convex integer programming, where we offer a new approach, thus removing the complexity’s exponential dependence in the dimension.

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B55 Computational aspects related to convexity
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Ardila, F.; Benedetti, C.; Doker, J., Matroid polytopes and their volumes, Discrete Comput. Geom., 43, 4, 841-854, (2010) · Zbl 1204.52016
[2] Avis, D.; Bremner, D.; Seidel, R., How good are convex hull algorithms?, Comput. Geom., 7, 265-301, (1997) · Zbl 0877.68119
[3] Avis, D.; Fukuda, K., A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom., 8, 295-313, (1992) · Zbl 0752.68082
[4] Billera, L.; Filliman, P.; Sturmfels, B., Constructions and complexity of secondary polytopes, Adv. Math., 83, 2, 155-179, (1990) · Zbl 0714.52004
[5] Boissonnat, J.-D.; Devillers, O.; Hornus, S., Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension, (ACM Symp. on Comp. Geometry, (2009)), 208-216 · Zbl 1380.68382
[6] Bussieck, M.; Lübbecke, M., The vertex set of a 0/1-polytope is strongly p-enumerable, Comput. Geom., 11, 2, 103-109, (1998) · Zbl 0912.68206
[7] De Loera, J.; Hemmecke, R.; Onn, S.; Rothblum, U.; Weismantel, R., Convex integer maximization via graver bases, J. Pure Appl. Algebra, 213, 8, 1569-1577, (2009) · Zbl 1284.05026
[8] De Loera, J.; Rambau, J.; Santos, F., Triangulations: structures for algorithms and applications, Algorithms and Computation in Mathematics, vol. 25, (2010), Springer · Zbl 1207.52002
[9] Edmonds, J.; Pulleyblank, W.; Lovász, L., Brick decompositions and the matching rank of graphs, Combinatorica, 2, 3, 247-274, (1982) · Zbl 0521.05035
[10] Emiris, I.; Fisikopoulos, V.; Konaxis, C.; Peñaranda, L., An oracle-based, output-sensitive algorithm for projections of resultant polytopes, Int. J. Comput. Geom. Appl., 23, 397-423, (2013) · Zbl 1297.68238
[11] Fukuda, K., From the zonotope construction to the Minkowski addition of convex polytopes, J. Symb. Comput., 38, (2004) · Zbl 1121.52020
[12] Fukuda, K.; Weibel, C., Computing all faces of the Minkowski sum of V-polytopes, (Canad. Conf. Comp. Geom., (2005)), 253-256
[13] Gelfand, I.; Kapranov, M.; Zelevinsky, A., Discriminants, resultants and multidimensional determinants, (1994), Birkhäuser Boston · Zbl 0827.14036
[14] Gritzmann, P.; Hufnagel, A., On the algorithmic complexity of Minkowski’s reconstruction problem, J. Lond. Math. Soc., 2, 5-9, (1999)
[15] Gritzmann, P.; Sturmfels, B., Minkowski addition of polytopes: computational complexity and applications to Gröbner bases, SIAM J. Discrete Math., 6, 2, 246-269, (1993) · Zbl 0798.68157
[16] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2, (1993), Springer · Zbl 0837.05001
[17] Huggins, P., Ib4e: a software framework for parametrizing specialized LP problems, (Iglesias, A.; Takayama, N., Mathematical Software - ICMS, Lect. Notes Comput. Sci., vol. 4151, (2006), Springer), 245-247 · Zbl 1230.90130
[18] Joswig, M.; Kaibel, V.; Körner, F., On the k-systems of a simple polytope, Isr. J. Math., 129, 1, 109-117, (2002) · Zbl 1009.52021
[19] Khachiyan, L., A polynomial algorithm in linear programming, Sov. Math. Dokl., 20, 1, 191-194, (1979) · Zbl 0409.90079
[20] Malajovich, G., 2014. Computing mixed volume and all mixed cells in quermassintegral time. ArXiv e-prints. · Zbl 1383.65050
[21] Masada, T.; Imai, H.; Imai, K., Enumeration of regular triangulations, (ACM Symp. on Comp. Geometry, SoCG ’96, (1996)), 224-233 · Zbl 0925.68445
[22] McMullen, P., The maximum numbers of faces of a convex polytope, Mathematika, 17, 179-184, (1971) · Zbl 0217.46703
[23] Michiels, T.; Cools, R., Decomposing the secondary Cayley polytope, Discrete Comput. Geom., 23, 367-380, (2000) · Zbl 0957.52003
[24] Onn, S.; Rothblum, U., Convex combinatorial optimization, Discrete Comput. Geom., 32, 4, 549-566, (2004) · Zbl 1179.90289
[25] Onn, S.; Rothblum, U., The use of edge-directions and linear programming to enumerate vertices, J. Comb. Optim., 14, 153-164, (2007) · Zbl 1157.90482
[26] Onn, S.; Rothblum, U.; Tangir, Y., Edge-directions of standard polyhedra with applications to network flows, J. Glob. Optim., 33, 1, 109-122, (Sep. 2005)
[27] Orevkov, S., The volume of the Newton polytope of a discriminant, Russ. Math. Surv., 54, 5, 1033-1034, (1999) · Zbl 0962.14032
[28] Pfeifle, J.; Rambau, J., Computing triangulations using oriented matroids, (Joswig, M.; Takayama, N., Algebra, Geometry and Software Systems, (2003), Springer Berlin, Heidelberg), 49-75 · Zbl 1027.52015
[29] Schneider, R., Convex bodies: the brunn-Minkowski theory, (1993), Cambridge University Press · Zbl 0798.52001
[30] Stanley, R., Combinatorics and commutative algebra, (2004), Birkhäuser Boston
[31] Sturmfels, B., On the Newton polytope of the resultant, J. Algebr. Comb., 3, 207-236, (1994) · Zbl 0798.05074
[32] Ziegler, G., Lectures on polytopes, (1995), Springer · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.