Algorithms for optimal outlier removal

被引：17

作者：

Atanassov, Rossen ^{[1
]}

Bose, Prosenjit ^{[1
]}

Couture, Mathieu ^{[1
]}

Maheshwari, Anil ^{[1
]}

Morin, Pat ^{[1
]}

Paquette, Michel ^{[1
]}

Smid, Michiel ^{[1
]}

Wuhrer, Stefanie ^{[1
]}

机构：

[1] Carleton Univ, Sch Comp Sci, 1125 Colonel By Dr, Ottawa, ON K1S 5B6, Canada

来源：

JOURNAL OF DISCRETE ALGORITHMS | 2009年 / 7卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Computational geometry; Outlier removal; Computational statistics;

D O I：

10.1016/j.jda.2008.12.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We consider the problem of removing c points from a set S of n points so that the remaining point set is optimal in some sense. Definitions of optimality we consider include having minimum diameter, having minimum area (perimeter) bounding box, having minimum area (perimeter) convex hull. For constant values of c, all our algorithms run in O(n logn) time. (C) 2009 Elsevier B. V. All rights reserved.

引用

页码：239 / 248

页数：10

共 19 条

[1] FINDING K-POINTS WITH MINIMUM DIAMETER AND RELATED PROBLEMS [J].

AGGARWAL, A ;

IMAI, H ;

KATOH, N ;

SURI, S .

JOURNAL OF ALGORITHMS, 1991, 12 (01) :38-56

[2]

Atanassov R., 2006, P 18 CANAD C COMP GE

[3]

Ben-Or Michael, 1983, P 15 ANN ACM S THEOR, P80

[4] Low-dimensional linear programming with violations [J].

Chan, TM .

SIAM JOURNAL ON COMPUTING, 2005, 34 (04) :879-893

[5] ON THE CONVEX LAYERS OF A PLANAR SET [J].

CHAZELLE, B .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) :509-517

[6] Vertex Cover: Further observations and further improvements [J].

Chen, J ;

Kanj, IA ;

Jia, WJ .

JOURNAL OF ALGORITHMS, 2001, 41 (02) :280-301

[7]

Clarkson K. L., 1988, Proceedings of the Fourth Annual Symposium on Computational Geometry, P12, DOI 10.1145/73393.73395

[8]

Dobkin D.P., 1983, COMPUTATIONAL GEOMET, V1, P181

[9]

Downey Rodney G., 1999, MG COMP SCI

[10]

Eckhoff J., 1993, HDB CONVEX GEOMETRY, VB. NorthHolland, P389

← 1 2 →