Paths Around Obstacles.
Al Jubeh, Marwan Ibrahim.
- Connectivity augmentation is an important area of study in optimization. For a given graph, a connectivity augmentation problem asks to augment the graph (add edges) such that the augmented graph has the desired connectivity. Motivated by the problem of making a given non-crossing geometric graph 3-vertex connected, we consider the following augmentation problem: for a non-crossing geometric graph... read moregiven in the form of convex obstacles inside a triangular container, augment the graph such that each obstacle has three disjoint paths to the containerâ��s boundary. We prove a lower bound on the number of edges needed for the augmentation, and also give an augmentation algorithm, which provides an upper bound. Furthermore, motivated by the problem where the obstacles not only must have three disjoint paths to the boundary, but where those paths are also required to be locally-geodesic. We attempt to find an algorithm that would produce three disjoint locally-geodesic paths to the vertices of a triangular container from any point in the free space that is surrounded by line-segment obstacles. We document the various attempts we made to produce such an algorithm, and present counterexamples where these approaches fail. We conclude by presenting a promising line of attack for which we have not been able to find a counterexample.read less