Convex Decompositions

D. P. Cervone ; W. S. Zwicker

Journal of convex analysis, Tome 16 (2009) no. 2, pp. 367-376.

Résumé

We consider decompositions S of a closed, convex set P into smaller, closed and convex regions. The thin convex" decompositions are those having a certain strong convexity property as a set of sets. Thin convexity is directly connected to our intended application in voting theory (see the second author, "Consistency without neutrality in voting rules: when is a vote an average?" and "A characterization of the rational mean neat voting rules", to appear in Mathematical and Computer Modelling, special issue on Mathematical Modeling of Voting Systems and Elections: Theory and Applications, ed. by A. Belenky, 2008), via the consistency property for abstract voting systems. The facial decompositions are those for which each intersecting pair of regions meet at a common face. The class of neat decompositions is defined by a separation property, neat separability by a hyperplane, applied to the regions. The regular decompositions are those whose regions, when we take cross sections by lines, reduce to closed intervals, any two of which are equal, or are disjoint, or overlap only at their endpoints. Our main result is that for polytopes P these four classes of decompositions are the same. The Voronoi decompositions of P are those whose regions are determined by the point (chosen from a designated finite subset Y of P) to which they are closest. These form a fifth class of decompositions, which is strictly contained in any of the first four classes.

Détail

Classification : 52B11, 91B12
Mots-clés : Convex set, decomposition, consistent voting system, hyperplane separation properties, Voronoi regions, regular decomposition, neat decomposition