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₁ and p₂ in P (and q₁ and q₂ in Q) to build two bridges p₁q₁ and p₂q₂ 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⁶ log n) time. (2) These results hold even if the bridges between p_i and q_i, i∈{1,2}, are geodesic. (3) We show the general problem is NP-hard: given m disjoint polygons P₁,..,P_m, add two bridges between P_i and P_i+1, i∈ [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.

© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.