The Maximum Distance Problem and Minimum Spanning Trees

Abstract

Given a compact E⊂Rn and s>0, the maximum distance problem seeks a compact and connected subset of Rn of smallest one dimensional Hausdorff measure whose s-neighborhood covers E. For E⊂R2, we prove that minimizing over minimum spanning trees that connect the centers of balls of radius s, which cover E, solves the maximum distance problem. The main difficulty in proving this result is overcome by the proof of a key lemma which states that one is able to cover the s-neighborhood of a Lipschitz curve Γ in R2 with a finite number of balls of radius s, and connect their centers with another Lipschitz curve Γ∗, where H1 (Γ∗) is arbitrarily close to H1(Γ). We also present an open source package for computational exploration of the maximum distance problem using minimum spanning trees, available at github.com/mtdaydream/MDP_MST.