On the Twin Bridges Problem in Polygons
摘要
In this paper, we investigate the twin bridges problem in polygons, whose counterpart on trees has been studied recently. Given two disjoint simple polygons P and Q, each with at most n vertices, the problem is to find two vertices \(p_1\) and \(p_2\) in P (and \(q_1\) and \(q_2\) in Q) to build two bridges \(p_1q_1\) and \(p_2q_2\) such that the constrained diameter of the resulting geometric structure (e.g., a polygon with a hole when the two bridges do not intersect), i.e., the maximum of the shortest distance between two vertices in P, Q, or just in one of them, through at least one of the bridges, is minimized. The main results are summarized as follows: (1) If P and Q are arbitrary polygons, the problem can be solved in \(O(n^6\log n)\) time. (2) These results hold even if the bridges between \(p_i\) and \(q_i\) , \(i\in \{1,2\}\) , are geodesic. (3) We show the general problem is NP-hard: given m disjoint polygons \(P_1,...,P_m\) , add two bridges between \(P_i\) and \(P_{i+1}\) , \(i\in [m-1]\) , such that the constrained diameter of the resulting geometric structure (ideally, a polygon with multiple holes, but could be more complex if some of the bridges intersect) is minimized.