Approximating minimum Steiner point trees in Minkowski planes

DOI10.1002/NET.20376MaRDI QIDQ3064040zbMATH OpenOpenAlexDBLPWikidataFDO

Authors M. Brazil, C. J. Ras, D. A. Thomas

Publication date 20 December 2010

Published in Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2987

zbMATH Keywords

bounded edge-length

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05)

Abstract: Given a set of points, we define a minimum Steiner point tree to be a tree interconnecting these points and possibly some additional points such that the length of every edge is at most 1 and the number of additional points is minimized. We propose using Steiner minimal trees to approximate minimum Steiner point trees. It is shown that in arbitrary metric spaces this gives a performance difference of at most $2n-4$, where $n$ is the number of terminals. We show that this difference is best possible in the Euclidean plane, but not in Minkowski planes with parallelogram unit balls. We also introduce a new canonical form for minimum Steiner point trees in the Euclidean plane; this demonstrates that minimum Steiner point trees are shortest total length trees with a certain discrete-edge-length condition.

Recommendations

• The 1-Steiner-Minimal-Tree problem in Minkowski-spaces
• Approximating Steiner trees and forests with minimum number of Steiner points
• A tight lower bound for the Steiner ratio in Minkowski planes
• Approximations for Steiner trees with minimum number of Steiner points
• scientific article; zbMATH DE number 742979

Cites work

• Approximation schemes for NP-hard geometric optimization problems: a survey
• Approximations for Steiner trees with minimum number of Steiner points
• Bottleneck Steiner trees in the plane
• Canonical forms and algorithms for Steiner trees in uniform orientation metrics
• Euclidean Steiner minimum trees: An improved exact algorithm
• Minimal Steiner trees for rectangular arrays of lattice points
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Steiner Minimal Trees
• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• Steiner tree problems in computer communication networks.
• The Fermat--Torricelli problem in normed planes and spaces
• Wire segmenting for buffer insertion based on RSTP-MSP

Cited in

(10)

• Minimum Steiner trees on a set of concyclic points and their center
• Exact computation of Steiner minimal trees in the plane
• scientific article; zbMATH DE number 1099658 (Why is no real title available?)
• Approximating Steiner trees and forests with minimum number of Steiner points
• Quadtree, ray shooting and approximate minimum weight Steiner triangulation
• IDENTIFYING STEINER MINIMAL TREES ON FOUR POINTS IN SPACE
• The 1-Steiner-Minimal-Tree problem in Minkowski-spaces
• Approximate Euclidean Steiner trees
• Minimum rectilinear Steiner tree of \(n\) points in the unit square
• A geometric characterisation of the quadratic min-power centre

This page was built for publication: Approximating minimum Steiner point trees in Minkowski planes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3064040)