Computing the Smallest T-Shaped Polygon Containing k Points
Michiel Smid, Vanam Srilakshmi · International Journal of Computer Mathematics · 2002
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 m k ) 2 ( k 2 + k log n )) and uses O ( n log n ) space.