How good are convex hull algorithms?

*(English)*Zbl 0877.68119Summary: A convex polytope \(P\) can be specified in two ways: as the convex hull of the vertex set \(\mathcal V\) of \(P\), or as the intersection of the set \(\mathcal H\) of its facet-inducing halfspaces. The vertex enumeration problem is to compute \(\mathcal V\) from \(\mathcal H\). The facet enumeration problem is to compute \(\mathcal H\) from \(\mathcal V\). These two problems are essentially equivalent under point/hyperplane duality. They are among the central computational problems in the theory of polytopes. It is open whether they can be solved in time polynomial in \(|{\mathcal H}|+|{\mathcal V}|\) and the dimension. In this paper we consider the main known classes of algorithms for solving these problems. We argue that they all have at least one of two weaknesses: inability to deal well with “degeneracies”, or, inability to control the sizes of intermediate results. We then introduce families of polytopes that exercise those weaknesses. Roughly speaking, fat-lattice or intricate polytopes cause algorithms with bad degeneracy handling to perform badly; dwarfed polytopes cause algorithms with bad intermediate size control to perform badly. We also present computational experience with trying to solve these problems on these hard polytopes, using various implementations of the main algorithms.

##### MSC:

68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |

52B55 | Computational aspects related to convexity |

65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |

PDF
BibTeX
XML
Cite

\textit{D. Avis} et al., Comput. Geom. 7, No. 5--6, 265--301 (1997; Zbl 0877.68119)

Full Text:
DOI

##### References:

[1] | Armand, P., Bounds on the number of vertices of polyhedra, Ann. oper. res., 47, 249-269, (1993) · Zbl 0786.90034 |

[2] | Avis, D.; Bremner, D., How good are convex hull algorithms?, (), 20-28 |

[3] | Avis, D.; Deza, A., Solitaire cones, () |

[4] | 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 |

[5] | B. Bradford Barber, D.P. Dobkin and H. Huhdanpaa, The quickhull algorithm for convex hull, ACM Trans. on Mathematical Software, to appear. · Zbl 0884.65145 |

[6] | Barnette, D.W., The minimum number of vertices of a simple polytope, Israel J. math., 8, 304-308, (1971) · Zbl 0201.24301 |

[7] | Bayer, M.M.; Lee, C.W., Combinatorial aspects of convex polytopes, (), 485-534 · Zbl 0789.52014 |

[8] | Brøndsted, A., Introduction to convex polytopes, (1981), Springer, |

[9] | Ceder, G.; Garbulsky, G.; Avis, D.; Fukuda, K., Ground states of a ternary lattice model with nearest and next-nearest neighbor interactions, Phys. rev. B, 49, 1-7, (1994) |

[10] | Chand, D.; Kapur, S., An algorithm for convex polytopes, J. ACM, 17, 78-86, (1970) · Zbl 0199.50902 |

[11] | Chazelle, B., An optimal convex hull algorithm in any fixed dimension, Discrete comput. geom., 10, 377-409, (1993) · Zbl 0786.68091 |

[12] | Chvátal, V., Linear programming, (1983), Freeman, New York · Zbl 0318.05002 |

[13] | Clarkson, K.L., More output-sensitive geometric algorithms, (), 695-702 |

[14] | Clarkson, K.L.; Shor, P.W., Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental, (), 12-17 |

[15] | Deza, A.; Deza, M.; Fukuda, K., On skeletons, diameters and volumes of metric polyhedra, () |

[16] | Dyer, M.E., The complexity of vertex enumeration methods, Math. oper. res., 8, 3, 381-402, (1983) · Zbl 0531.90064 |

[17] | Edelsbrunner, H., Algorithms in combinatorial geometry, (), 147-158 |

[18] | K. Fukuda, cdd Reference Manual, Version 0.55 (EPFL, Lausanne, Switzerland). |

[19] | K. Fukuda, mit71-61.ine solved, Private communication (1996). |

[20] | Gal, T., Selected bibliography on degeneracy, Ann. oper. res., 47, 1-8, (1993) · Zbl 0786.90093 |

[21] | Grishukin, V.P., Computing extreme rays of the metric cone for seven points, European J. combinatorics, 13, 153-165, (1992) · Zbl 0760.05058 |

[22] | Grünbaum, B., Convex polytopes, (1967), Interscience, London · Zbl 0163.16603 |

[23] | Haiman, M., A simple and relatively efficient triangulation of the n-cube, Discrete comput. geom., 6, 287-289, (1991) · Zbl 0727.68044 |

[24] | Kirkman, T.P., On the enumeration of x-hedra having triedal summits and an (x − 1)-gonal base, Philos. trans. roy. soc. London ser. A, 146, 399-411, (1856) |

[25] | Klee, V., Polytope pairs and their relationship to linear programming, Acta math., 133, 1-25, (1974) · Zbl 0307.90042 |

[26] | Klee, V.; Minty, G.J., How good is the simplex method?, (), 159-175 |

[27] | L’Ecuyer, P., Efficient and portable combined random number generators, Comm. ACM, 31, (1988) |

[28] | Matoušek, J.; Schwarzkopf, O., Linear optimization queries, (), 16-25 |

[29] | McMullen, P., The maximal number of faces of a convex polytope, Mathematica, 17, 179-184, (1970) · Zbl 0217.46703 |

[30] | Motzkin, T.S.; Raiffa, H.; Thompson, G.L.; Thrall, R.M., The double description method, (), 51-73 · Zbl 0050.14201 |

[31] | Provan, J.S., Efficient enumeration of the vertices of polyhedra associated with network LP’s, Math. programming, 63, 47-64, (1994) · Zbl 0792.90045 |

[32] | Rote, G., Degenerate convex hulls in high dimensions without extra storage, (), 26-32 |

[33] | R. Seidel, The nature and meaning of perturbations in geometric computing, Discrete Comput. Geom., to appear. · Zbl 0892.68100 |

[34] | Seidel, R., A convex hull algorithm optimal for point sets in even dimensions, () |

[35] | Seidel, R., Output-size sensitive algorithms for constructive problems in computational geometry, () |

[36] | also: Technical Report TR 86-784. |

[37] | Swart, G., Finding the convex hull facet by facet, J. algorithms, 17-48, (1985) · Zbl 0563.68041 |

[38] | Ziegler, G., () |

[39] | Bremner, D., Incremental convex hull algorithms are not output sensitive, (), 26-35 · Zbl 0924.68192 |

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.