Minkowski-plane bead-gap tightness conjecture for Steiner minimum paths

Let NN be a set of nn terminals in a Minkowski plane MM with unit ball BB, and let TST_S and ToptT_{\mathrm{opt}} be a dMd_M-SMT and a dMd_M-MSPT on NN, respectively. Minkowski-plane bead-gap conjecture. The upper bound

beads(TS)beads(Topt)2n4\mathrm{beads}(T_S)-\mathrm{beads}(T_{\mathrm{opt}})\leq 2n-4

is tight if and only if BB is not a parallelogram. This conjecture concerns the sharp performance gap between Steiner minimum trees and minimum Steiner point trees in Minkowski planes; the supplied text gives no resolution.

Sources & referencesView supporting material

Primary source

M. Brazil, C. J. Ras and D. A. Thomas, “Approximating Minimum Steiner Point Trees in Minkowski Planes”, arXiv:1307.2987 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.