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.
Constructing the visibility graph for polygonal objects is well studied @cite_16 @cite_22 @cite_28 @cite_29 @cite_25 @cite_0 @cite_10 . The fastest algorithm for it takes @math time @cite_22 , where @math is the size of the visibility graph. For the relevant visibility graph problem @cite_4 @cite_31 @cite_0 (or building the relevant visibility graph ) on splinegons, two special cases have been studied. When @math contains @math convex objects of @math complexity each, the problem is solvable in @math time @cite_31 , where @math is the number of free common tangents. If @math contains @math convex polygons , as in @cite_4 @cite_0 , then the problem is solvable in @math time; an open question was posed in @cite_4 to solve this case in @math time, where @math is the number of free common tangents. Note that our optimal @math time result is better than the solution desired by this open question.
@cite_4 @cite_22 @cite_28 @cite_29 @cite_0 @cite_31 @cite_16 @cite_10 @cite_25
1482503584 1963903160 1583742799 2147097381
The visibility graph of a set of nonintersecting polygonal obstacles in the plane is an undirected graph whose vertex set consists of the vertices of the obstacles and whose edges are pairs of vertices @math such that the open line segment between u and v does not intersect any of the obstacles. The visibility graph is an important combinatorial structure in computational geometry and is used in applications such as solving visibility problems and computing shortest paths. This paper presents an algorithm that computes the visibility graph of a set of obstacles in time @math , where E is the number of edges in the visibility graph and n is the total number of vertices in all the obstacles. The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesnik (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71–93, 1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesnik by showing that for any two vertices v and w in a graph of diameter 2, if deg(v)≤deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most l collinear vertices has connectivity at least @math , which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that l=4 we improve this bound to two thirds of the minimum degree. We present an algorithm to find an Euclidean Shortest Path from a source vertex @math to a sink vertex @math in the presence of obstacles in @math . Our algorithm takes @math time and @math space. Here, @math is the time to triangulate the polygonal region, @math is the number of obstacles, and @math is the number of vertices. This bound is close to the known lower bound of @math time and @math space. Our approach involve progressing shortest path wavefront as in continuous Dijkstra-type method, and confining its expansion to regions of interest. This paper describes a new algorithm for constructing the set of free bitangents of a collection of n disjoint convex obstacles of constant complexity. The algorithm runs in time O(n log n + k), where k is the output size, and uses O(n) space. While earlier algorithms achieve the same optimal running time, this is the first optimal algorithm that uses only linear space. The visibility graph or the visibility complex can be computed in the same time and space. The only complicated data structure used by the algorithm is a splittable queue, which can be implemented easily using red-black trees. The algorithm is conceptually very simple, and should therefore be easy to implement and quite fast in practice. The algorithm relies on greedy pseudotriangulations, which are subgraphs of the visibility graph with many nice combinatorial properties. These properties, and thus the correctness of the algorithm, are partially derived from properties of a certain partial order on the faces of the visibility complex.