Optimizing a Strip Separating Two Polygons

We consider the problem of finding a strip separating between two polygons, whose intersection with a third (convex) polygon is of maximum area. We present an optimal linear-time algorithm for computing the optimum strip. When the third polygon is not convex, the running time of the algorithm is quadratic in the size of the input. The application in mind is the piecewiselinear surface interpolation in simple branching cases, where the sought volume branches from one contour in one slice into two contours in the other slice. Key Words: plane sweep; branching surfaces; polyhedra; surface reconstruction. 1 Introduction In this paper we consider the following problem in the plane: Problem 1 Given two line-separable polygons P; Q and a convex polygon R, find the strip S separating between P and Q, whose intersection with R has maximum area. Note that not only do P and Q not intersect but their convex hulls are also disjoint. The third polygon R may intersect P and/or Q. We present a...