Please use this identifier to cite or link to this item:
http://hdl.handle.net/20.500.11861/7656
Title: | Steiner trees in general nonuniform orientations |
Authors: | Li Y.Y. Prof. LEUNG Kwong Sak Wong C.K. |
Issue Date: | 2001 |
Source: | Computing (Vienna/New York), 2001, vol. 66 (1), pp. 41 - 78 |
Journal: | Computing (Vienna/New York) |
Abstract: | In this paper we consider Steiner minimum trees (SMT) in the plane, where the connections can only be along a given set of fixed but arbitrary (not necessarily uniform) orientations. The orientations define a metric, called the general orientation metric, Aσ, where σ is the number of orientations. We prove that in Aσ metric, there exists an SMT whose Steiner points belong to an (n - 2)-level grid. This result generalizes a result by Lee and Shen [11], and a result by Du and Hwang [5]. In the former case, the same result was obtained for the special case when all orientations are uniform, while in the latter case the same result was proven for the special case when there are only three arbitrary orientations. We then modify the proof used in the main result for the special case when σ = 3, i.e., only three arbitrary orientations are considered, and obtain a better result, which states that there exists an SMT whose Steiner points belong to an [n-1/2]-level grid. The result has also been obtained by Lin and Xue [9] using a different approach. |
Type: | Peer Reviewed Journal Article |
URI: | http://hdl.handle.net/20.500.11861/7656 |
ISSN: | 0010485X |
DOI: | 10.1007/s006070170038 |
Appears in Collections: | Applied Data Science - Publication |
Find@HKSYU Show full item record
SCOPUSTM
Citations
1
checked on Nov 17, 2024
Page view(s)
29
Last Week
1
1
Last month
checked on Nov 21, 2024
Google ScholarTM
Impact Indices
Altmetric
PlumX
Metrics
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.