Packing and covering with balls on Busemann surfaces

Abstract: In this note we prove that for any compact subset

S

of a Busemann surface

(m a t h c a l S, d)

(in particular, for any simple polygon with geodesic metric) and any positive number

d e l t a

, the minimum number of closed balls of radius

d e l t a

with centers at

m a t h c a l S

and covering the set

S

is at most 19 times the maximum number of disjoint closed balls of radius

d e l t a

centered at points of

S

:

u (S) l e h o (S) l e 19 u (S)

, where

h o (S)

and

u (S)

are the covering and the packing numbers of

S

by

d e l t a

-balls.

Review text

Let \(\mathcal{F}\) be a collection of subsets of a domain \(X\). The \textit{set covering problem} asks to find a subcollection of \(\mathcal{F}\) of minimal size whose union is \(X\); similarly, the \textit{set packing problem} asks to find the maximum number of pairwise disjoint subsets of \(\mathcal{F}\). The article under review considers these problems using balls of equal radii of subsets of certain surfaces called Busemann surfaces. A \textit{Busemann space} is a geodesic metric space in which the distance function between any two geodesics is convex, and a \textit{Busemann surface} is a Busemann space which is a \(2\)-dimensional manifold. The main result of the paper is the following: let \(S\) be a compact subset of a Busemann surface and \(\delta\) an arbitrary positive number. Denote by \(\rho_{\delta}(S)\) the minimum number of (closed) balls of radius \(\delta\) in a covering of \(S\), and denote by \(\nu_{\delta}(S)\) the maximum number of (closed) balls in a packing of \(S\). Then \(\rho_{\delta}(S) \leq 19\nu_{\delta}(S)\). Section \(2\) starts by recalling the basic notions and results related to Busemann surfaces, geodesic metric spaces, and coverings of metric spaces by closed and open balls. The section culminates with statements of the main results in the article. Section \(3\) consists of proofs of the results stated in Section \(2\). In the course of proving the main results, multiple auxiliary lemmas are also proven. The fourth and final section is reserved for asking three open questions related to the content of the article.

Recommendations

Cites work

Cited in

(5)

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)