Minimum-width double-strip and parallelogram annulus (Q784485): Difference between revisions

A planar strip is the closed set of points between two parallel lines, and its width is the (orthogonal) distance between these lines. A double strip is the closure of the difference of an outer strip and an included inner strip, its width being half the difference between both strips' widths. A parallelogram annulus is obtained from two double strips of different orientations by intersecting their outer strips and deleting the interior of the intersected inner strips, its width being the larger of both double strip widths. Given a set of \(n\) points \(P\) in the plane and a subset \(Q\) of size \(k\), a minimum-width double strip containing \(Q\) with outer strip containing \(P\) can be computed in \(O(n\log n+kn)\) time using the geometric dual. With a same complexity one may compute such a minimum-width double strip for all stepwise reduced \(Q\) in prespecified order. A minimum-width parallelogram annulus containing \(P\) is computable in \(O(n)\) time for two fixed orientations, in \(O(n^2)\) time for a single fixed orientation, and in \(O(n^3\log n)\) time when both orientations are free.