Carleton University
Technical Report TR-06-07
May 1, 2006
Removing Outliers to Minimize Area and Perimeter
R. Aanassov, P. Morin, S. Wuhrer
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(f(c)+log n)) time algorithm that solves this problem when “smallest” is taken to mean least area or least perimeter.