Search

Given a point set K of terminals in the plane, the octilinear Steiner tree problem is to find a shortest tree that interconnects all terminals and edges run either in horizontal, vertical, or ±45° diagonal direction. This problem is fundamental for the novel octilinear routing paradigm in VLSI design, the so-called X-architecture. As the related rectilinear and the Euclidian Steiner tree problem are well-known to be NP-hard, the same was widely believed for the octilinear Steiner tree problem but left open for quite some time. In this paper, we prove the NP-completeness of the decision version of the octilinear Steiner tree problem. We also show how to reduce the octilinear Steiner tree problem to the Steiner tree problem in graphs of polynomial size with the following approximation guarantee. We construct a planar graph of size $O(\frac{n^2}{\varepsilon^2})$ which contains a (1 + ε)–approximation of a minimum octilinear Steiner tree for every ε > 0 and n = |K|. Hence, we can apply any α–approximation algorithm for the Steiner tree problem in graphs (for planar graphs, Borradaile et al. very recently presented a polynomial time approximation scheme) and achieve an (α + ε)–approximation bound for the octilinear Steiner tree problem. This approximation guarantee also holds for the more difficult case where the Steiner tree has to avoid blockages (obstacles bounded by octilinear polygons). [ABSTRACT FROM AUTHOR]

The Euclidean centre (centre of the smallest enclosing sphere) of a set of points P in two or more dimensions is unstable; small perturbations at only a few points of P can result in an arbitrarily large relative change in the position of the Euclidean centre. Any centre function more stable than the Euclidean centre is eccentric; that is, its associated radius exceeds the radius of the smallest enclosing circle for some point sets P. Motivated by applications in mobile facility location (in which clients move continuously with some maximum velocity) we seek alternative notions of centrality that are stable while maintaining low eccentricity. In general there is a trade-off; centre functions with lower eccentricity are less stable. In an attempt to balance the conflicting goals of closeness of approximation and stability, we apply the Steiner centre, traditionally defined for convex polytopes, as a centre function of a set of points in the plane. Although previously defined, the notion of a Steiner centre had not been analyzed in terms of its approximation of the Euclidean centre. Exploiting the equivalence of the two definitions of the Steiner centre established by Shephard,27 we prove the stability of the Steiner centre is π/4 and show that the associated radius is at most 1.1153 times the Euclidean radius of any point set P. It follows that a mobile facility located at the Steiner centre of the positions of a set of mobile clients remains close to the Euclidean centre of the clients yet never moves with relative velocity that exceeds 4/π. [ABSTRACT FROM AUTHOR]

We introduce a new algorithm to convert triangular meshes of polygonal regions, with or without holes, into strictly convex quadrilateral meshes of small bounded size. Our algorithm includes all vertices of the triangular mesh in the quadrilateral mesh, but may add extra vertices (called Steiner points). We show that if the input triangular mesh has t triangles, our algorithm produces a mesh with at most $\lfloor\frac{3t}{2}\rfloor+2$ quadrilaterals by adding at most t+2 Steiner points, one of which may be placed outside the triangular mesh domain. We also describe an extension of our algorithm to convert constrained triangular meshes into constrained quadrilateral ones. We show that if the input constrained triangular mesh has t triangles and its dual graph has h connected components, the resulting constrained quadrilateral mesh has at most $\lfloor\frac{3t}{2}\rfloor+4h$ quadrilaterals and at most t+3h Steiner points, one of which may be placed outside the triangular mesh domain. Examples of meshes generated by our algorithm, and an evaluation of the quality of these meshes with respect to a quadrilateral shape quality criterion are presented as well. [ABSTRACT FROM AUTHOR]

For a given set of points in the Euclidean plane, a minimum network (a Steiner minimal tree) can be constructed using a geometric method, called Melzak's construction. The core of the Melzak construction is to replace a pair of terminals adjacent to the same Steiner point with a new terminal. In this paper we prove that the Melzak construction can be generalized to constructing Steiner minimal trees for circles so that either the given points (terminals) are constrained on the circles or the terminal edges are tangent to the circles. Then we show that the generalized Melzak construction can be used to find minimum networks separating and surrounding circular objects or to find minimum networks connecting convex and smoothly bounded objects and avoiding convex and smoothly bounded obstacles. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]