Premium
Reducing the Steiner problem in four uniform orientations
Author(s) -
Lin GuoHui,
Xue Guoliang
Publication year - 2000
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/1097-0037(200007)35:4<287::aid-net8>3.0.co;2-r
Subject(s) - steiner tree problem , combinatorics , computer science , mathematical optimization , mathematics
We studied the Steiner tree problem in four uniform orientations where any line, half‐line, or line segment must be on a line which makes an angle of ( i π)/4 with the positive x ‐axis, for some i ∈ {0, 1, 2, 3}, and the distance between two points is measured as the length of the shortest polygonal path connecting them. We show that for any set P of n terminal points there exists a Steiner minimum tree interconnecting P such that all Steiner points are in ⌈2 n /3⌉ − 1 ( P ), the (⌈(2 n )/3⌉ − 1) st ‐generation grid points of P . Our result improves the previous best result which guarantees that for any set P of n terminal points there is a Steiner minimum tree in which all Steiner points are in n − 2 ( P ). © 2000 John Wiley & Sons, Inc.