Shortest Directed Networks in the Plane
- PDF / 737,555 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 106 Downloads / 183 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Shortest Directed Networks in the Plane Alastair Maxwell1 • Konrad J. Swanepoel1 Received: 18 March 2019 / Revised: 14 April 2020 Ó The Author(s) 2020
Abstract Given a set of sources and a set of sinks as points in the Euclidean plane, a directed network is a directed graph drawn in the plane with a directed path from each source to each sink. Such a network may contain nodes other than the given sources and sinks, called Steiner points. We characterize the local structure of the Steiner points in all shortest-length directed networks in the Euclidean plane. This characterization implies that these networks are constructible by straightedge and compass. Our results build on unpublished work of Alfaro, Campbell, Sher, and Soto from 1989 and 1990. Part of the proof is based on a new method that uses other norms in the plane. This approach gives more conceptual proofs of some of their results, and as a consequence, we also obtain results on shortest directed networks for these norms. Keywords Euclidean Steiner problem Shortest directed network Normed plane Straightedge and compass
Mathematics Subject Classification Primary 05C20 Secondary 49Q10 52A40 90B10
1 Introduction In the well-studied Euclidean Steiner problem, a finite set of points in the plane is given, and the problem is to find a shortest network interconnecting all points. Its fascinating history is given a definitive treatment by Brazil et al. [4]. What distinguishes this problem from the well-known Minimal Spanning Tree problem, is This work is partially based on a dissertation of the first author written as part of an MSc in Applicable Mathematics at the LSE. & Konrad J. Swanepoel [email protected] 1
Department of Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK
123
Graphs and Combinatorics
that such a network (necessarily a tree) may contain new points, called Steiner points. The degree of such a Steiner point is always 3, and the angle between any two incident edges is 120 . In fact, any such tree is constructible using straightedge and compass. Despite the simplicity of this local structure, it is NP-hard to compute such a shortest network. On the other hand, there is an exact algorithm (GeoSteiner) that can feasibly compute these networks for given point sets of size in the thousands. For more detail, see Chapter 1 of Brazil and Zachariasen [5]. A directed version of this problem was introduced by Frank Morgan for undergraduate research at Williams College in the late 1980s [1–3]. In this problem, a set of sources and a set of sinks in the plane are given, and the object is to find a shortest directed network containing a directed path from each source to each sink. As these directed networks are not necessarily trees, they are much harder to study, and even their existence is non-trivial [2]. See Fig. 4(b) for an example of a shortest directed network that has a cycle. There is no known algorithm for finding such ne
Data Loading...
