×

Counterexamples to the connectivity conjecture of the mixed cells. (English) Zbl 0929.52008

The authors give two counterexamples to a conjecture of J. Verschelde, K. Gatermann and R. Cools [Discrete Comput. Geom. 16, No. 1, 69-112 (1996; Zbl 0854.68111)] and of P. Pedersen. It concerns a connectivity property of the mixed cells of subdivisions for Minkowski sums of polytopes and is of interest in connection with certain algorithms. The first counterexample is in dimension two, the second is in dimension three and refutes the conjecture even for subdivisions induced by liftings.

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)

Citations:

Zbl 0854.68111
Full Text: DOI