Premium
Approximating minimum Steiner point trees in Minkowski planes
Author(s) -
Brazil M.,
Ras C. J.,
Thomas D. A.
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20376
Subject(s) - steiner tree problem , mathematics , combinatorics , parallelogram , euclidean geometry , point (geometry) , minkowski space , tree (set theory) , plane (geometry) , discrete mathematics , geometry , computer science , artificial intelligence , robot
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 2 n ‐ 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. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010