The Maximum Distance Problem and Minimum Spanning Trees

Article Sidebar

PDF
Cite as:
Enrique G. Alvarado, Bala Krishnamoorthy, Kevin R. Vixie, The Maximum Distance Problem and Minimum Spanning Trees, Int. J. Anal. Appl., 19 (5) (2021), 633-659.

Main Article Content

Enrique G. Alvarado, Bala Krishnamoorthy, Kevin R. Vixie

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.

Article Details

References

  1. L. Ambrosio and P. Tilli. Topics on analysis in metric spaces, volume 25. Oxford University Press, 2004.
  2. A. Antoniadis, K. Fleszar, R. Hoeksma, and K. Schewior. A PTAS for Euclidean TSP with Hyperplane Neighborhoods. In: Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, 2019: pp. 1089-1105.
  3. G. Buttazzo, E. Oudet, E. Stepanov, Optimal Transportation Problems with Free Dirichlet Regions, in: G. dal Maso, F. Tomarelli (Eds.), Variational Methods for Discontinuous Structures, Birkhäuser Basel, Basel, 2002: pp. 41-65.
  4. D. Cohen-Steiner, H. Edelsbrunner, J. Harer, Stability of Persistence Diagrams, Discrete Comput. Geom. 37 (2007), 103-120.
  5. G. David and S. Semmes. Analysis of and on uniformly rectifiable sets, volume 38. American Mathematical Society, 1993.
  6. M. de Berg, J. Gudmundsson, M.J. Katz, et al. TSP with neighborhoods of varying size, J. Algorithms. 57 (2005), 22-36.
  7. H. Edelsbrunner and J. L. Harer. Computational Topology An Introduction. American Mathematical Society, 2009.
  8. K. J. Falconer. The geometry of fractal sets, volume 85. Cambridge University Press, 1986.
  9. H. Federer. Geometric Measure Theory. Classics in Mathematics. Springer-Verlag, 1969.
  10. S. Gillies. Shapely: Geometric objects, predicates, and operations. Available at https://pypi.org/project/Shapely/. Version 1.7, accessed June 2020.
  11. P. W. Jones. Rectifiable sets and the traveling salesman problem. Invent. Math. 102(1) (1990), 1-15.
  12. J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7(1) (1956), 48-50.
  13. A. Lemenant. A presentation of the average distance minimizing problem. J. Math. Sci. 181 (2012), 820-836.
  14. M. Miranda Jr., E. Paolini, and E. Stepanov. On one-dimensional continua uniformly approximating planar sets. Calc. Var. Part. Differ. Equ. 27(3) (2006), 287-309.
  15. K. Okikiolu. Characterization of subsets of rectifiable curves in Rn. J. Lond. Math. Soc. 2(2) (1992), 336-348.
  16. Emanuele Paolini and Eugene Stepanov. Qualitative properties of maximum distance minimizers and average distance minimizers in Rn. J. Math. Sci. 122(3) (2004), 3290-3309.
  17. R. Schul, Subsets of rectifiable curves in Hilbert space-the analyst's TSP, J. Anal. Math. 103 (2007), 331-375.
  18. Y. Teplitskaya. Regularity of maximum distance minimizers. J. Math. Sci. 232(2) (2018), 164-169.
  19. Y. Teplitskaya. On regularity of maximal distance minimizers, 2019. arXiv:1910.07630.