Approximating minimum Steiner point trees in Minkowski planes

DOI10.1002/NET.20376zbMATH Open1206.90199DBLPjournals/networks/BrazilRT10arXiv1307.2987OpenAlexW1980159248WikidataQ61714618 ScholiaQ61714618MaRDI QIDQ3064040FDOQ3064040

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

Publication date: 20 December 2010

Published in: Networks (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

bounded edge-length

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

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

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)