Intersecting ellipses induced by a max-sum matching

DOI10.1007/S10898-023-01312-WMaRDI QIDQ6154397FDO

Authors Polina Barabanshchikova, Aleksandr A. Polyanskii

Publication date 15 February 2024

Published in Journal of Global Optimization (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationalternating cycleTverberg theoreminfinite descentmax-sum matching

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Discrete geometry (52C99) Metric geometry (51F99) Mathematical programming (90Cxx)

Abstract: For an even set of points in the plane, choose a max-sum matching, that is, a perfect matching maximizing the sum of Euclidean distances of its edges. For each edge of the max-sum matching, consider the ellipse with foci at the edge's endpoints and eccentricity $2/sqrt3$. Using an optimization approach, we prove that the convex sets bounded by these ellipses intersect, answering a Tverberg-type question of Andy Fingerhut from 1995.

Recommendations

• On maximum-sum matchings of points
• Center of maximum-sum matchings of bichromatic points
• Intersecting diametral balls induced by a geometric graph. II
• Euclidean maximum matchings in the plane -- local to global
• Euclidean maximum matchings in the plane -- local to global

Cites work

• scientific article; zbMATH DE number 439380 (Why is no real title available?)
• A Generalization of Radon's Theorem
• Drawing Hamiltonian cycles with no large angles
• Intersecting diametral balls induced by a geometric graph
• Matching points with disks with a common intersection
• On generalizations of Radon's theorem and the Ham sandwich theorem
• On maximum-sum matchings of points
• On minimum stars and maximum matchings.
• Partitions of points into simplices with \(k\)-dimensional intersection. I: The conic Tverberg's theorem
• Tverberg's theorem, disks, and Hamiltonian cycles

Cited in

(2)

• Euclidean maximum matchings in the plane -- local to global
• Intersecting diametral balls induced by a geometric graph. II

This page was built for publication: Intersecting ellipses induced by a max-sum matching

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