Minimum-width annulus with outliers: Circular, square, and rectangular cases

We study the problem of computing a minimum-width annulus with outliers. Specifically, given a set of n points in the plane and an integer k with 1≤k≤n, 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 i...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2019-05, Vol.145, p.16-23
Main Authors: Ahn, Hee-Kap, Ahn, Taehoon, Bae, Sang Won, Choi, Jongmin, Kim, Mincheol, Oh, Eunjin, Shin, Chan-Su, Yoon, Sang Duk
Format: Article
Language:English
Subjects:
Annulus
Computational geometry
Exact algorithm
Geometric shape matching
Outlier
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the problem of computing a minimum-width annulus with outliers. Specifically, given a set of n points in the plane and an integer k with 1≤k≤n, 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. •We present first/improved algorithms for a minimum-width annulus with k outliers.•For the circular case, our algorithm runs in O(k(kn)3/2+ε) time.•For the square case, our algorithm runs in O(k2nlog⁡n) time.•For the rectangular case, our algorithm runs in O(nlog⁡n+k4log2⁡n) or O(nk2log⁡k+k4log2⁡k) time.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2019.01.004