Packing and covering with balls on Busemann surfaces

DOI10.1007/S00454-017-9872-0zbMATH Open1372.52021arXiv1508.00778OpenAlexW2179481075MaRDI QIDQ2358828FDOQ2358828

Bertrand Estellon, Guyslain Naves, Victor Chepoi

Publication date: 16 June 2017

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

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.

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

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

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)

Cites Work

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

Cited In (5)

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

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)