Optimal interconnection trees in the plane. Theory, algorithms and applications (Q2339762)

The focus of this monograph is the geometric Steiner tree problem, i.e., how to optimally connect, in a geometric plane, a collection of \(n\) given terminals, together with an additional set of Steiner points, in terms of a measuring metric. Notice that the problem is so named because the resulted network is always a tree. A quite accessible introductory chapter on the Euclidean version of this problem starts with the classic Fermat-Torricelli problem, i.e., given three points \(a\), \(b\) and \(c\) lying in an Euclidean plane, how to find a (Steiner) point \(s\) such that the sum of the distances from \(s\) to \(a\), \(b\) and \(c\) is minimized. An elegant and elementary solution, based on a rotation technique, is presented in details to set the tone for the rest of the journey. The general Steiner tree problem for the Euclidean space is then naturally introduced, where for a given collection of terminals \(N\), a connected network, \(T, N \subset V(T),\) is constructed such that \(\sum_{e \in E(T)} |e|\) is minimized, where \(|e|\) stands for the Euclidean length of an edge \(e\) of \(T\); and \(V(T) \setminus N\) is referred to as the Steiner points. Besides exposing various geometric, topological, structural, and complexity properties, numerous efficient minimal Steiner tree construction algorithms such as the Melzak-Huang algorithm and the Smith algorithm, as well as the general GeoSteiner algorithm, are also presented and discussed. A naïve algorithm to construct a minimum Steiner tree is to enumerate all the possible ways to connect the given \(n\) terminals with at most \(n-2\) Steiner points, called Steiner topologies, then apply, e.g., the Melzak-Huang algorithm, to obtain the respective Steiner trees, and finally achieve a minimum one by identifying a subset of these trees, which interconnect all the terminals, and the Steiner points, with minimum length. This approach is certainly infeasible because of the existence of super-exponential number of Steiner topologies. It turns out that most of the Steiner topologies are not associated with Steiner trees, and, even if they are, most of the resulted Steiner trees are either not minimum or do not satisfy certain necessary geometric/structural properties. Such an observation leads to the initiating phase of the GeoSteiner algorithm where doomed structures are eliminated at an early stage; and the remaining collection should contain all the components of at least one minimum Steiner tree, which are then concatenated into a desired minimum Steiner tree. The latter concatenation phase is also independent of the measuring metric. It is stated that the GeoSteiner algorithm is one of the most efficient algorithms in this area. For example, it takes about ten seconds to construct a minimum Steiner tree for one thousand of terminals lying in an Euclidean space. This chapter, just as all the other chapters of this book, ends with a section on applications, discussing, e.g., efficient network construction, especially on printed circuit design, and the relationship of this problem to other areas of mathematics, and its extension to higher dimension of spaces. Chapter 2, on fixed orientation Steiner trees, study the problem, still within the Euclidean space, but each edge of the constructed network is composed of straight segments restricted to a fixed set of orientations, each coming with a weight. The goal is then to construct an interconnection network of minimum weight. With proper tuning, the GeoSteiner algorithm can also be adapted to solve a special version of the fixed orientation Steiner tree problem, i.e., the one associated with a uniform orientation, corresponding to a Minkowski plane where the unit circle is a regular \(2\lambda\)-gon. It is reported that it takes about an hour to construct such a minimum Steiner tree when \(\lambda \leq 8,\) and takes just a minute when \(\lambda=4,\) both for one thousand terminal points. This type of Steiner tree construction problem finds applications in printed board routing, channel routing, and general chip design by, e.g., changing the usual horizontal and vertical wiring (\(\lambda=2\)) to hexagonal wiring\ (\(\lambda=3\)), or adding in diagonal wires (\(\lambda=4\)). As the number of layers in modern chip design goes beyond ten, even larger values of \(\lambda\) can be considered. On the other hand, in the most important applications, the number of orientations is rather limited. For example, most of the current chip design uses only rectilinear\ (Manhattan) orientations, where the main objective is to minimize the total length of the used wires. Because of this important application, the rectilinear Steiner tree problem\ (\(\lambda=2\)) is treated separately in Chapter 3. Although this special problem is NP-complete, thanks to the existence of the Hwang canonic form for every full component of a rectilinear Steiner tree, efficient practical algorithms, especially a variant of the general GeoSteiner algorithm, can solve instances where more than one thousand terminals are involved. Details of such construction and estimation algorithms, as well as special properties for such rectilinear Steiner trees, are presented, analyzed and discussed. A brief, but informative, introduction of the chip design process as well as the role as played by the rectilinear Steiner tree in such a process and its practical extension are given in the application section of this chapter. Other than the Euclidean, and fixed orientation planes, the Steiner tree problem can also be exactly solved in terms of some other cost functions and/or constraints, when it possesses nice geometric properties. Among the important cases as discussed in Chapter 4 is the gradient-constraints Steiner trees, based on the gradient metrics, which is defined in terms of the gradient of two points, i.e., the slope of the related line segment. This problem can find applications in underground mine design, where respective tunnels need to be connected into a system. Various geometric properties are explored, which supports a conjecture that it is possible to construct this type of minimum Steiner trees in some cases, although the general gradient constraint problems is also proved to be NP-hard, just as all the other problems as discussed in this book. Obstacle-avoiding Steiner trees, where no path in the resulting Steiner tree goes through the interior of an obstacle, represented as an area; and general \(k\)-Steiner tree, where at most \(k\) Steiner points can be used, are also explored. The construction of wireless network is discussed as an important application of the latter problem. As mentioned earlier, the focus of this book is the geometric Steiner tree problem, where the locations of the Steiner points are not restricted in a Minkowski plane, although, in practice, they often are. Such a rather restrictive situation can be modeled as the Steiner tree problem in graphs and hypergraphs, where both the terminals and the Steiner points are subsets of a given set of vertices in a graph/hypergraph. The task now is to select the optimal edges and vertices to form a minimal tree. This combinatorial problem is perhaps among the most studied variants of the Steiner tree problem, and many theoretical results and practical algorithms have appeared in the literature. Chapter 5, the last chapter of this book, provides an extensive survey of such results, as well as some of the main formulating and tackling techniques, such as dynamic programming and integer programming. A clearly related and well-known problem is the minimum spanning tree problem, where no Steiner pointers can be used when a minimum network is constructed to connect a given collection of terminals. One aspect of their relationship is represented as the Steiner ratio, i.e., the ratio between the cost of a minimum Steiner tree and that of a minimum spanning tree for any set of given \(n\) terminals when \(n\) is arbitrarily large. For the Euclidean case, the lower and upper bounds for such a ratio are given as 0.82416874 and \(\sqrt{3}/2,\) respectively. It is not a surprise that the Steiner ratio for the fixed orientation case depends on the value of \(\lambda\). In particular, the Steiner ratio for the rectilinear case, where \(\lambda=2\), is shown to be 2/3. This book is rich in content, technical in nature, rigorous in reasoning, while well written and quite readable. The 150 figures, including 135 colored ones, certainly helped. Besides rigorous and mostly complete proofs for most of the results and sufficient and relevant 433 references spread all over the book, the authors clearly have real-world applications in their minds behind most of the technical results. They apparently talked the talk, while walking the walk. I am particularly impressed with many thorough and helpful footnotes that provide background and/or historical information related to various issues, notions and results. This monograph is also intended as a textbook at a graduate level, thus comes with a decent collection of exercises, with varying difficulty degrees, at the end of each chapter, mostly assigned in a relevant context throughout the main text. I would like to see solutions to at least some of them are provided in a later edition at least, to the instructors. It would also be ideal to associate a difficulty degree with each exercise. This book is mostly self-contained, and numerous references have also been made use of for a supplemental purpose, especially in Chapter~5. On the other hand, although references are given for the notion of Minkowski plane, some brief and intuitive introduction to this notion should be included for the sake of completeness, considering the abstract nature of this notion and its important role to a variety of applications as described in this book.