Intersecting diametral balls induced by a geometric graph. II

DOI10.1016/J.DISC.2023.113694MaRDI QIDQ6080152zbMATH OpenFDO

Authors Polina Barabanshchikova, Aleksandr A. Polyanskii

Publication date 30 October 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.10706

zbMATH Keywords

alternating cycleconvex optimizationinfinite descentmax-sum matchingmax-sum treeTverberg theorem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Helly-type theorems and geometric transversal theory (52A35) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: For a graph whose vertices are points in $mathbb{R}^d$, consider the closed balls with diameters induced by its edges. The graph is called a Tverberg graph if these closed balls intersect. A max-sum tree of a finite point set $Xsubsetmathbb{R}^d$ is a tree with vertex set $X$ that maximizes the sum of Euclidean distances of its edges among all trees with vertex set $X$. Similarly, a max-sum matching of an even set $Xsubsetmathbb{R}^d$ is a perfect matching of $X$ maximizing the sum of Euclidean distances between the matched points among all perfect matchings of $X$. We prove that a max-sum tree of any finite point set in $mathbb{R}^d$ is a Tverberg graph, which generalizes a recent result of Abu-Affash et al., who established this claim in the plane. Additionally, we provide a new proof of a theorem by Bereg et al., which states that a max-sum matching of any even point set in the plane is a Tverberg graph. Moreover, we proved a slightly stronger version of this theorem.

Recommendations

• Intersecting diametral balls induced by a geometric graph
• Intersecting ellipses induced by a max-sum matching
• Tverberg's theorem, disks, and Hamiltonian cycles
• On maximum-sum matchings of points

Cites work

• A Generalization of Radon's Theorem
• Matching points with disks with a common intersection
• On maximum-sum matchings of points
• Quantitative Helly-Type Theorems
• Tverberg's theorem, disks, and Hamiltonian cycles

Cited in

(3)

• Intersecting diametral balls induced by a geometric graph
• Intersecting ellipses induced by a max-sum matching
• Center of maximum-sum matchings of bichromatic points

This page was built for publication: Intersecting diametral balls induced by a geometric graph. II

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