Intersecting diametral balls induced by a geometric graph

DOI10.1007/S00454-022-00457-XMaRDI QIDQ6151026zbMATH OpenFDO

Authors Olimjoni Pirahmad, Aleksandr A. Polyanskii, Alexey Vasilevskii

Publication date 9 February 2024

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

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

zbMATH Keywords

\(\alpha\)-lensealternating cyclearrangements of convex bodiesgeometric graphhalving lineHamiltonian cycleinfinite descentperfect matchingred-blue matchingTverberg's theorem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Metric geometry (51F99) Convex sets without dimension restrictions (aspects of convex geometry) (52A05) Helly-type theorems and geometric transversal theory (52A35) Other problems of combinatorial convexity (52A37)

Abstract: For a graph whose vertex set is a finite set of points in the Euclidean $d$-space consider the closed (open) balls with diameters induced by its edges. The graph is called a (an open) Tverberg graph if these closed (open) balls intersect. Using the idea of halving lines, we show that ($i$) for any finite set of points in the plane, there exists a Hamiltonian cycle that is a Tverberg graph; ($ii$) for any $n$ red and $n$ blue points in the plane, there exists a perfect red-blue matching that is a Tverberg graph. Also, we prove that ($iii$) for any even set of points in the Euclidean $d$-space, there exists a perfect matching that is an open Tverberg graph; ($iv$) for any $n$ red and $n$ blue points in the Euclidean $d$-space, there exists a perfect red-blue matching that is a Tverberg graph.

Recommendations

• Intersecting diametral balls induced by a geometric graph. II
• Tverberg's theorem, disks, and Hamiltonian cycles
• A local criterion for Tverberg graphs
• A Colored Version of Tverberg's Theorem

Cites work

• A Colored Version of Tverberg's Theorem
• A Generalization of Radon's Theorem
• A survey of mass partitions
• Alternating cycles in edge-partitioned graphs
• An extension of the Erdős-Szekeres theorem on large angles
• ARRANGEMENTS OF HOMOTHETS OF A CONVEX BODY
• Covering with Euclidean boxes
• Drawing Hamiltonian cycles with no large angles
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 3368644 (Why is no real title available?)
• 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
• Optimal bounds for a colorful Tverberg-Vrećica type problem
• Optimal bounds for the colored Tverberg problem
• Partitions of points into simplices with k-dimensional intersection. I: The conic Tverberg's theorem
• Positive-fraction intersection results and variations of weak epsilon-nets
• Tverberg's theorem, disks, and Hamiltonian cycles

Cited in

(5)

• Intersecting diametral balls induced by a geometric graph. II
• Intersecting ellipses induced by a max-sum matching
• Acute tours in the plane
• Piercing diametral disks induced by edges of maximum spanning trees
• On maximum-sum matchings of bichromatic points

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

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