Removing Outliers to Minimize Area and Perimeter
Rossen Atanassov, Pat Morin, Stefanie Wuhrer · 2006
Abstract. We consider the problem of removing c points from a set S of n points so that the resulting point set has the smallest possible convex hull. Our main result is an O � n � � � � � 4c c 2c (3c) + log n time algorithm that solves this problem when “smallest ” is taken to mean least area or least perimeter. 1