An optimal algorithm for constructing an optimal bridge between two simple rectilinear polygons

摘要

Let P and Q be two disjoint rectilinear polygons in the plane. We say P and Q are in Case 1 if there exists a rectilinear line segment to connect them; otherwise, we say they are in Case 2. In this paper, we present optimal algorithms for solving the following problem. Given two disjoint rectilinear polygons P and Q in the plane, we want to add a rectilinear lien segment to connect them when they are in Case 1, or add two rectilinear line segments, one is vertical and the other is horizontal, to connect P and Q when they are in Case 2. Our objective is to minimize the maximum of the L1-distances between points in one polygon and points in the other polygon through one or two line segments. Let V(P) and V(Q) be the vertex sets of P and Q, respectively, and let |VP)|=m and |V(P)|=m and |V(Q)|=n. In this paper, we present O(m+n) time algorithms for the above two cases.