A geometric study of the split decomposition

DOI10.1007/S00454-006-1243-1MaRDI QIDQ2505228zbMATH OpenOpenAlexFDO

Authors Hiroshi Hirai

Publication date 4 October 2006

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-006-1243-1

zbMATH Keywords

discrete concave functionfinite metric spacepolyhedral convex function

Mathematics Subject Classification ID

Convexity of real functions of several variables, generalizations (26B25) Metric spaces, metrizability (54E35) Convex programming (90C25) Combinatorial optimization (90C27)

Review text

It is shown that any polyhedral convex function may be written in an essentially unique way as a weighted sum of distance functions to hyperplanes and another undecomposable polyhedral convex function. Dually this corresponds to obtaining the maximum zonotopic Minkowsky summand of a pointed polyhedron. Considering a finite metric as a particular discrete concave function this construction is shown to be equivalent to the Bandelt-Dress split decomposition for finite metric spaces [\textit{H.-J. Bandelt} and \textit{A. W. M. Dress}, Adv. Math. 92, No. 1, 47--105 (1992; Zbl 0789.54036)], which thereby also extends to certain non-metric discrete functions violating the triangle inequality. It is shown that the combinatorics of the splits involved in split decompositions correspond to geometric properties of a hyperplane arrangement and a point configuration.

Recommendations

• The Buneman index via polyhedral split decomposition
• A note on M-convexity in polyhedral split decomposition of distances
• A canonical decomposition theory for metrics on a finite set
• \(T\)-theory: An overview
• Split decomposition over an Abelian group. I: Generalities

Cited in

(32)

• A canonical decomposition theory for metrics on a finite set
• The splitting method and Poincaré's theorem. I: The geometric part
• A geometric characteristic splitting in all dimensions
• Multi-splits and tropical linear spaces from nested matroids
• Hyperconvexity and tight-span theory for diversities
• The geometry of the Hilton splitting
• \(T\)-theory: An overview
• On tight spans for directed distances
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• Fundamental polytopes of metric trees via parallel connections of matroids
• Matroids from hypersimplex splits
• Recent developments in discrete convex analysis
• Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
• The hyperdeterminant and triangulations of the 4-cube
• The split decomposition of a \(k\)-dissimilarity map
• Trees, tight-spans and point configurations
• A tractable class of binary VCSPs via M-convex intersection
• From weakly separated collections to matroid subdivisions
• Splits and tight spans of convex polytopes
• Totally split-decomposable metrics of combinatorial dimension two
• Six points suffice: How to check for metric consistency
• On the facets of the secondary polytope
• Split decomposition over an Abelian group. I: Generalities
• Peakless functions on graphs
• Subdivisions of Hypersimplices: With a View Toward Finite Metric Spaces
• A note on M-convexity in polyhedral split decomposition of distances
• Subtree distances, tight spans and diversities
• Buneman graphs, partial splits and subtree distances
• The Buneman index via polyhedral split decomposition
• The split decomposition of a tridiagonal pair
• Compatible decompositions and block realizations of finite metrics
• Totally splittable polytopes

This page was built for publication: A geometric study of the split decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2505228)