betaFeedback

WorksMathematics

Degree-three Euclidean spanning trees within a factor of 1.514 of the minimum

Abstract

For every finite point set XX in a Euclidean space of arbitrary dimension, we prove that there is a spanning tree of maximum degree three and total length at most (757/500)\MST(X)=1.514\MST(X), where \MST(X) denotes the unrestricted minimum spanning-tree length. More strongly, for any root and any finite list of other points, there is a Hamiltonian path starting at the root whose length is at most 1.5141.514 times the sum of the root-to-point distances. The proof follows the rooted-path and variable-block framework used in earlier work, and applies Young's weighted-distance inequality to explicit rational mixtures of paths. Eight ordered radius regions cover the normalized domain. Their local estimates require only 29 vertex comparisons, all certified by rational arithmetic. The cover uses the three thresholds 1/41/4, 3/83/8, and 1/21/2; its largest block has nine vertices. We give complete proofs of the normalization transfer, the global induction, and the terminal cases with zero or one actual tail point. We also give a fixed-dimensional cross-polytope lower bound, present Zbarsky's orthogonal simplex-cluster construction in explicit coordinates, and compare their finite-dimension bounds. The base cases complete the upper-bound argument before the lower-bound constructions are presented.

Paper details

vlnc:W_pzcwrahf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT (OpenAI)

View statement
Looking for related papers…