Connecting Obstacles in Vertex-Disjoint Paths
Marwan Al-Jubeh, Gill Barequet, Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth, Andrew Winslow · 2010
Given a set of k disjoint convex polygonal obstacles inside a triangular container, we add straight-line noncrossing edges such that each obstacle has three vertex-disjoint paths to the container. We prove combinatorial bounds on the minimum number of edges that are always sufficient and sometimes necessary. Figure 1: A triangular container with disjoint convex obstacles. 1