1. Shortest Directed Networks in the Plane
- Author
-
Alastair Maxwell and Konrad J. Swanepoel
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,Straightedge ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,Mathematical proof ,01 natural sciences ,Local structure ,Theoretical Computer Science ,Combinatorics ,Mathematics - Metric Geometry ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Compass ,Euclidean geometry ,FOS: Mathematics ,Mathematics - Combinatorics ,05C20, 49Q10, 52A40, 90B10 ,Discrete Mathematics and Combinatorics ,QA Mathematics ,Mathematics - Optimization and Control ,Mathematics ,Metric Geometry (math.MG) ,021107 urban & regional planning ,Directed graph ,Optimization and Control (math.OC) ,010201 computation theory & mathematics ,Computer Science - Computational Geometry ,Combinatorics (math.CO) ,MathematicsofComputing_DISCRETEMATHEMATICS - 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., 21 pages, 14 figures. To appear in Graphs and Combinatorics
- Published
- 2020