×

zbMATH — the first resource for mathematics

Convex hulls, oracles, and homology. (English) Zbl 1121.52030
Summary: A new algorithm for the convex hull problem, which is based on a reduction to a combinatorial decision problem COPLETENESSC, which in turn can be solved by a simplicial homology computation. Like other convex hull algorithms, our algorithm is polynomial (in the size of input plus output) for simplicial or simple input. We show that the “no”-case of COMPLETENESSC has a certificate that can be checked in polynomial time (if integrity of the input is guaranteed).
An extended abstract version of this paper “Polytope verification by homology computation”, has appeared in the Proceedings of EuroCG, Berlin, March 26–28, 2001, pp. 142–145.

MSC:
52B55 Computational aspects related to convexity
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W30 Symbolic computation and algebraic computation
Software:
cdd; polymake
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Avis, D., A revised implementation of the reverse search vertex enumeration algorithm, (), 177-198 · Zbl 0960.68171
[2] Avis, D., 2001. lrs—a C implementation of the reverse search vertex enumeration algorithm, version 4.1
[3] Avis, D.; Bremner, D.; Seidel, R., How good are convex hull algorithms?, (), Comput. Geom. 7 (5-6), 265-301 · Zbl 0877.68119
[4] Avis, D.; Fukuda, K., A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, (), Discrete Comput. Geom. 8 (3), 295-313 · Zbl 0752.68082
[5] Björner, A., Topological methods, (), 1819-1872 · Zbl 0851.52016
[6] Bremner, D., Incremental convex hull algorithms are not output sensitive, Discrete comput. geom., 21, 1, 57-68, (1999) · Zbl 0924.68192
[7] Bremner, D.; Fukuda, K.; Marzetta, A., Primal-dual methods for vertex and facet enumeration, (), Discrete Comput. Geom. 20 (3), 333-357 · Zbl 0910.68217
[8] Chazelle, B., An optimal convex hull algorithm in any fixed dimension, Discrete comput. geom., 10, 4, 377-409, (1993) · Zbl 0786.68091
[9] Freund, R.M.; Orlin, J.B., On the complexity of four polyhedral set containment problems, Math. program., 33, 2, 139-145, (1985) · Zbl 0581.90060
[10] Fukuda, K., 2000. frequently asked questions in polyhedral computation
[11] Fukuda, K., 2003. CDD—a C-implementation of the double description method; cddlib, version 0.93
[12] Gawrilow, E.; Joswig, M., 1997-2003. polymake. version 2.0: a software package for analyzing convex polytopes
[13] Gawrilow, E.; Joswig, M., Polymake: an approach to modular software design in computational geometry, (), 222-231 · Zbl 1375.68136
[14] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, Algorithms and combinatorics, vol. 2, (1993), Springer-Verlag Berlin · Zbl 0837.05001
[15] Joswig, M.; Kaibel, V.; Pfetsch, M.E.; Ziegler, G.M., 2000. ambiguous incidences of unbounded polyhedra. electronic geometry models, Model No. 2000.05.001 · Zbl 1122.52300
[16] Joswig, M.; Kaibel, V.; Pfetsch, M.E.; Ziegler, G.M., Vertex – facet incidences of unbounded polyhedra, Adv. geom., 1, 1, 23-36, (2001) · Zbl 0994.52009
[17] Kaibel, V.; Pfetsch, M.E., Some algorithmic problems in polytope theory, (), 23-48 · Zbl 1027.65032
[18] Lee, C.W., Subdivisions and triangulations of polytopes, (), 383-406
[19] Lovász, L., An algorithmic theory of numbers, graphs and convexity, CBMS-NSF regional conference series in applied mathematics, vol. 50, (1986), Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 0606.68039
[20] McCarthy, N.; Ogilvie, D.; Spitkovsky, I.; Zobin, N., Birkhoff’s theorem and convex hulls of Coxeter groups, Linear algebra appl., 347, 219-231, (2002) · Zbl 1042.51011
[21] McMullen, P., The maximum numbers of faces of a convex polytope, Mathematika, 17, 179-184, (1970) · Zbl 0217.46703
[22] Munkres, J.R., Elements of algebraic topology, (1984), Addison-Wesley Publishing Company Menlo Park, CA · Zbl 0673.55001
[23] Seidel, R., Small-dimensional linear programming and convex hulls made easy, Discrete comput. geom., 6, 5, 423-434, (1991) · Zbl 0747.90066
[24] Ziegler, G.M., ()
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.