Degree-three Euclidean spanning trees within a factor of 1.514 of the minimum
Source: arxiv.org/abs/2611.23703
For every finite point set $X$ 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.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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.23703
curl -X POST /api/v1/records/arxiv/2611.23703/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.23703/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'