caa a22 4500 465751547 CHVBK 20180323111835.0 cr unu---uuuuu 170327e19900301xx s 000 0 eng 10.1007/BF02250584 doi (NATIONALLICENCE)springer-10.1007/BF02250584 Shortest polygonal paths in space [Elektronische Daten] [R. Burkard, G. Rote, E. Yao, Z. Yu] Kürzeste Streckenzüge im Raum A classical problem of geometry is the following: given a convex polygon in the plane, find an inscribed polygon of shortest circumference. In this paper we generalize this problem to arbitrary polygonal paths in space and consider two cases: in the "open” case the wanted path of shortest length can have different start and end point, whereas in the "closed” case these two points must coincide. We show that finding such shortest paths can be reduced to finding a shortest path in a planar "channel”. The latter problem can be solved by an algorithm of linear-time complexity in the open as well in the closed case. Finally, we deal with constrained problems where the wanted path has to fulfill additional properties; in particular, if it has to pass straight through a further point, we show that the length of such a constrained polygonal path is a strictly convex function of some angle α, and we derive an algorithm for determining such constrained polygonal paths efficiently. Springer-Verlag, 1990 Shortest polygonal paths nationallicence shortest inpolygons nationallicence funnel nationallicence linear time algorithm nationallicence constrained paths nationallicence convex function nationallicence Burkard R. Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut Rote G. Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut Yao E. Mathematical Department, Zhejiang University, Hangzhou, P. R. China aut Yu Z. Mathematical Section, Forestry University Nanjing, Nanjing, P.R. China aut Computing Springer-Verlag 45/1(1990-03-01), 51-68 0010-485X 45:1<51 1990 45 607 https://doi.org/10.1007/BF02250584 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02250584 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Burkard R. Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut NATIONALLICENCE 700 1- Rote G. Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut NATIONALLICENCE 700 1- Yao E. Mathematical Department, Zhejiang University, Hangzhou, P. R. China aut NATIONALLICENCE 700 1- Yu Z. Mathematical Section, Forestry University Nanjing, Nanjing, P.R. China aut NATIONALLICENCE 773 0- Computing Springer-Verlag 45/1(1990-03-01), 51-68 0010-485X 45:1<51 1990 45 607 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer