Intersecting ellipses induced by a max-sum matching

DOI10.1007/S10898-023-01312-WarXiv2212.14200MaRDI QIDQ6154397FDOQ6154397

Authors: Polina Barabanshchikova, Aleksandr A. Polyanskii 

Publication date: 15 February 2024

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

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.

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)

Cites Work

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

Cited In (1)

• Euclidean maximum matchings in the plane -- local to global

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)