Packing and covering with balls on Busemann surfaces

DOI10.1007/S00454-017-9872-0MaRDI QIDQ2358828zbMATHOpenAlexFDO

Authors Victor Chepoi, Bertrand Estellon, Guyslain Naves

Publication date 16 June 2017

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

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

zbMATH Keywords

covering numberpacking numberballsBusemann surfaces

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Metric geometry (51F99) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Abstract: In this note we prove that for any compact subset $S$ of a Busemann surface $(mathcalS,d)$ (in particular, for any simple polygon with geodesic metric) and any positive number $delta$, the minimum number of closed balls of radius $delta$ with centers at $mathcalS$ and covering the set $S$ is at most 19 times the maximum number of disjoint closed balls of radius $delta$ centered at points of $S$: $u(S)leho(S)le19u(S)$, where $ho(S)$ and $u(S)$ are the covering and the packing numbers of $S$ by $delta$-balls.

Recommendations

• scientific article; zbMATH DE number 480248
• scientific article; zbMATH DE number 1182895
• scientific article; zbMATH DE number 3846365
• Sphere packings give an explicit bound for the Besicovitch covering theorem
• Bounds for several-disk packings of hyperbolic surfaces

Cites work

• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 1385418 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 2117213 (Why is no real title available?)
• Almost optimal set covers in finite VC-dimension
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Approximation algorithms for maximum independent set of pseudo-disks
• Computing the geodesic center of a simple polygon
• Covering a hypergraph of subgraphs
• Covering and coloring problems for relatives of intervals
• Covering nearly surface-embedded graphs with a fixed number of balls
• Covering planar graphs with a fixed number of balls
• Improved results on geometric hitting set problems
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Independent set of intersection graphs of convex objects in 2D
• Isometric embedding of Busemann surfaces into \(L_1\)
• Matching, edge-colouring, and dimers.
• Metric entropy and approximation
• Metric spaces, convexity and nonpositive curvature
• Nearest neighbor queries in metric spaces
• On Helly's theorem in geodesic spaces
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Packing and covering a tree by subtrees
• Piercing \(d\)-intervals
• Problems from CGCS Luminy, May 2007
• Transversals for families of translates of a two-dimensional convex compact set
• Uniform Central Limit Theorems
• VC-dimension and Erdős-Pósa property
• Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner

Cited in

(5)

• Packing and covering balls in graphs excluding a minor
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Ball packings in spaces of constant curvature and the simplicial density function
• Old and new challenges in Hadamard spaces
• Crystallographic Helly groups

This page was built for publication: Packing and covering with balls on Busemann surfaces

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