Computing an \(L_1\) shortest path among splinegonal obstacles in the plane

We reduce the problem of computing an \(L_1\) shortest path between two given points s and t in the given splinegonal domain \(\mathcal {S}\) to the problem of computing an \(L_1\) shortest path between two points in the polygonal domain. Our reduction algorithm defines a polygonal domain \(\mathcal {P}\) from \(\mathcal {S}\) by identifying a coreset of points on the boundaries of splinegons in \(\mathcal {S}\). Further, it transforms a shortest path between s and t among polygonal obstacles in \(\mathcal {P}\) to a shortest path between s and t among splinegonal obstacles in \(\mathcal {S}\). When \(\mathcal {S}\) is comprised of h pairwise disjoint simple splinegons defined with a total of n vertices, excluding the time to compute an \(L_1\) shortest path among simple polygonal obstacles in \(\mathcal {P}\), our reduction algorithm takes \(O(n + h \lg {n} + (\lg {h})^{1+\epsilon })\) 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}\) 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\) shortest path in the polygonal domain. Further, we have characterized few of the properties of \(L_1\) shortest paths among splinegons which could be of independent interest.