Optimizing a Corridor Between Two Polygons with an Application to Polyhedral Interpolation
Gill Barequet, Barbara Wolfers · 1996
We consider the problem of finding a corridor (a separating strip) between two polygons, whose intersection with a third (convex) polygon is of maximum area. The application in mind is the interpolation in simple branching cases, where the sought volume branches from one contour in one slice into two polygons in another parallel slice. We present a linear-time planesweep algorithm which computes such a corridor. When the third polygon is not convex the running time of the algorithm is quadratic in the size of the input. Keywords: surface reconstruction, plane-sweep, branching surfaces, slice interpolation, polyhedra. 1 Introduction The problem of reconstructing the boundary of a solid object from a series of parallel planar cross-sections has attracted much attention in the literature during the past two decades. The main motivations for this problem come from medical imaging applications and from geographic information systems. The input usually consists of a series of parallel pla...