Computing an $$L_1$$L1 shortest path among splinegonal obstacles in the plane

We reduce the problem of computing an $$L_1$$L1 shortest path between two given points s and t in the given splinegonal domain $$\mathcal {S}$$S to the problem of computing an $$L_1$$L1 shortest path between two points in the polygonal domain. Our reduction algorithm defines a polygonal domain $$\mathcal {P}$$P from $$\mathcal {S}$$S by identifying a coreset of points on the boundaries of splinegons in $$\mathcal {S}$$S. Further, it transforms a shortest path between s and t among polygonal obstacles in $$\mathcal {P}$$P to a shortest path between s and t among splinegonal obstacles in $$\mathcal {S}$$S. When $$\mathcal {S}$$S is comprised of h pairwise disjoint simple splinegons defined with a total of n vertices, excluding the time to compute an $$L_1$$L1 shortest path among simple polygonal obstacles in $$\mathcal {P}$$P, our reduction algorithm takes $$O(n + h \lg {n} + (\lg {h})^{1+\epsilon })$$O(n+hlgn+(lgh)1+ϵ) time. Here, $$\epsilon $$ϵ is a small positive constant [resulting from the triangulation of the free space using Bar-Yehuda and Chazelle (Int J Comput Geom Appl 4(4):475–481, 1994)]. For the special case of $$\mathcal {S}$$S comprising of concave-out splinegons, we have devised another reduction algorithm. This algorithm does not rely on the structures used in the algorithm (Inkulu and Kapoor in Comput Geom 42(9):873–884, 2009) to compute an $$L_1$$L1 shortest path in the polygonal domain. Further, we have characterized few of the properties of $$L_1$$L1 shortest paths among splinegons which could be of independent interest.