Minimum-Width Annulus with Outliers: Circular, Square, and Rectangular Cases

Abstract

We study the problem of computing a minimum-width annulus with outliers. Specifically, given a set of n points in the plane and a nonnegative integer kn, the problem asks to find a minimum-width annulus that contains at least n-k input points. The k excluded points are considered as outliers of the input points. In this paper, we are interested in particular in annuli of three different shapes: circular, square, and rectangular annuli. For the three cases, we present first and improved algorithms to the problem. © 2018, Springer International Publishing AG, part of Springer Nature.