Beiträge zur Algebra und GeometrieContributions to Algebra and Geometry
Vol. 45, No. 2, pp. 649-663 (2004)
|
|
Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Vol. 45, No. 2, pp. 649-663 (2004) |
|
|
Exactly solvable and unsolvable shortest network problems in 3D-spaceR. S. Booth, D. A. Thomas and J. F. WengSchool of Informatics and Engineering, The Flinders University of South Australia, GPO Box 2100, Adelaide 5001, Australia, e-mail: ray@infoeng.flinders.edu.au; ARC Special Research Center for Ultra-Broadband Information Networks, Department of Electrical and Electronic Engineering, The University of Melbourne, Victoria 3010, Australia, e-mail: d.thomas@ee.mu.oz.au; CUBIN, Department of Electrical and Electronic Engineering, Melbourne University, VIC 1030, Australia, e-mail: j.weng@ee.mu.oz.auAbstract: A problem is defined to be exactly solvable if its solution can be obtained by solving a sequence of polynomials using radicals. Therefore, if a problem is not exactly solvable, then we have to use approximation schemes for solving the problem. It has been proved that the shortest network problem in space is not exactly solvable even if the network spans only four points and even if the topology is known. On the other hand, if the network spans three points, then obviously the problem is exactly solvable. In a previous paper we have shown that the shortest network problem for three points is still exactly solvable if only one point is constrained on a straight line but it becomes non-exactly solvable if two points are constrained on straight lines. In this paper we continue to reduce the gap between the exact solvability and non-solvability by studying the shortest networks with gradient constraints. The motivation of this study also comes from a practical netnetwork problem: designing an underground mining network so that the ore in two underground deposits can be extracted through tunnels either directly to a vertical shaft and then hauled up to the ground, or extracted to a tunnel in an existing underground mining network and then transported to the ground. For technical reasons the gradient of any tunnel cannot be very steep. We prove that in the former case the shortest network problem is exactly solvable, while in the latter case the exact solvability depends on edge gradients. Moreover, we show that there are good iterative approximations for the non-exactly solvable shortest network problems in space. Keywords: Steiner network, unsolvability Classification (MSC2000): 05C05, 94C15 Full text of the article:
Electronic version published on: 9 Sep 2004. This page was last modified: 4 May 2006.
© 2004 Heldermann Verlag
|