Computing the smallest T-shaped polygon containing k points

A T-polygon is an axes-parallel polyon with eight edges having the shape of the letter T. We give an O(n)-time algorithm that decides, when given a set S of n points in the plane, whether a minimum-size T-polygon enclosing all points of S exists. Here, size refers to the area or perimeter of the T-polygon. If this minimum-size T-polygon exists, then our algorithm computes it in O(n log n) time if size refers to area, and in O(n) time if size refers to perimeter. We also give an algorithm that, when given the set S and an integer k, computes the minimum-size T-polygon that contains k points of S, or decides that this T-polygon does not exist. The latter algorithm has running time O(n 2(n-k)2(k2+k log n)) and uses O(n log n) space. © 2002 Taylor & Francis Ltd.