A fundamental problem in computational geometry is to compute an obstacle-avoiding Euclidean shortest path between two points in the plane. The case of this problem on polygonal obstacles is well studied. In this paper, we consider the problem version on curved obstacles, commonly modeled as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge (polygons are special splinegons). Each curved edge is assumed to be of O(1) complexity. Given in the plane two points s and t and a set of @math pairwise disjoint splinegons with a total of @math vertices, we compute a shortest s-to-t path avoiding the splinegons, in @math time, where k is a parameter sensitive to the structures of the input splinegons and is upper-bounded by @math . In particular, when all splinegons are convex, @math is proportional to the number of common tangents in the free space (called "free common tangents") among the splinegons. We develop techniques for solving the problem on the general (non-convex) splinegon domain, which also improve several previous results. In particular, our techniques produce an optimal output-sensitive algorithm for a basic visibility problem of computing all free common tangents among @math pairwise disjoint convex splinegons with a total of @math vertices. Our algorithm runs in @math time and @math space, where @math is the number of all free common tangents. Even for the special case where all splinegons are convex polygons, the previously best algorithm for this visibility problem takes @math time.
For a single splinegon @math , a shortest @math - @math path in @math can be found in @math time, and further, shortest paths from @math to all vertices of @math can be found in @math time @cite_5 .
@cite_5
2063244634
The goal of this paper is to show that the concept of the shortest path inside a polygonal region contributes to the design of efficient algorithms for certain geometric optimization problems involving simple polygons: computing optimum separators, maximum area or perimeter-inscribed triangles, a minimum area circumscribed concave quadrilateral, or a maximum area contained triangle. The structure for the algorithms presented is as follows: (a) decompose the initial problem into a low-degree polynomial number of optimization problems; (b) solve each individual subproblem in constant time using standard methods of calculus, basic methods of numerical analysis, or linear programming. These same optimization techniques can be applied to splinegons (curved polygons). First a decomposition technique for curved polygons is developed; this technique is substituted for triangulation in creating equally efficient curved versions of the algorithms for the shortest-path tree, ray-shooting, and two-point shortest path...