Shape fitting with outliers

Sariel Har-Peled, Yusu Wang · SCG '03 · 2003

Summary

This work proposes the first algorithms to handle outliers efficiently for the shape fitting problems considered, and relies on computing a subset of H of size of size O(k/e d-1) in near linear time.

Type: article
Published: 2003-06-08
Cited by: 69
References: 29
DOI: https://doi.org/10.1145/777792.777798
OpenAlex: https://openalex.org/W2074131282
Semantic Scholar: https://api.semanticscholar.org/CorpusID:7748348

Keywords

Outlier, Hyperplane, Algorithm, Approximation algorithm, Set (abstract data type)

References

Pattern ClassificationShigeo Abe — 2012
Vertical decomposition of shallow levels in 3-dimensional arrangements and its applicationsPankaj K. Agarwal, Alon Efrat, Micha Sharir — 1995
Optimal outlier removal in high-dimensional spacesJohn Dunagan, Santosh Vempala — 2004
New lower bounds for convex hull problems in odd dimensionsJeff Erickson — 1996
On geometric optimization with few violated constraintsJiřı́ Matoušek — 1994
Approximating extent measures of pointsPankaj K. Agarwal, Sariel Har-Peled, Kasturi Varadarajan — 2004
Algorithms for facility location problems with outliersMoses Charikar, Samir Khuller, David M. Mount — 2001
Iterated nearest neighbors and finding minimal polytopesDavid Eppstein, Jeff Erickson — 1993
Maintaining approximate extent measures of moving pointsPankaj K. Agarwal, Sariel Har-Peled — 2001
Support vector machinesAlessia Mammone, Marco Turchi, Nello Cristianini — 2008
On Constants for Cuttings in the PlaneJiřı́ Matoušek — 1998
Optimal outlier removal in high-dimensionalJohn Dunagan, Santosh Vempala — 2001
Applications of random sampling in computational geometry, IIKenneth L. Clarkson — 1988
Static and Dynamic Algorithms for k-Point Clustering ProblemsAmitava Datta, Hans‐Peter Lenhof, Christian Schwarz — 1993
New applications of random sampling in computational geometryKenneth L. Clarkson — 1987
On Enclosing k Points by a CircleJiřı́ Matoušek — 1995
Efficiently approximating the minimum-volume bounding box of a point set in three dimensionsGill Barequet, Sariel Har-Peled — 2025
Approximation and exact algorithms for minimum-width annuli and shellsPankaj K. Agarwal, Boris Aronov, Sariel Har-Peled — 1999
On levels in arrangements and voronoi diagramsKetan Mulmuley — 1991
Low-dimensional linear programming with violationsTimothy M. Chan — 2002

Cited by

Outlier Detection for DNA Fragment AssemblyChristina Boucher, Christine Lo, Daniel Lokshtanov — 2011
Linear Time Algorithm for Projective ClusteringHu Ding, Jinhui Xu — 2012
Data Imprecision in Computational GeometryMaarten Löffler — 2009
Algorithms - ESA 2003ESA 2003 Budapest, Di Battista, Giuseppe — 2003
epsilon-Kernel Coresets for Stochastic PointsLingxiao Huang, Jian Li, Jeff M. Phillips — 2014
Approximating extent measures of pointsPankaj K. Agarwal, Sariel Har-Peled, Kasturi Varadarajan — 2004
How to get close to the median shapeSariel Har-Peled — 2006
Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related ProblemsHu Ding, Jinhui Xu — 2014
On the Least Median Square ProblemJeff Erickson, Sariel Har-Peled, David M. Mount — 2004
Order-k α-hulls and α-shapesDmitry Krasnoshchekov, Valentin Polishchuk — 2014
Fast Algorithms for Computing the Smallest k-Enclosing CircleSariel Har-Peled, Soham Mazumdar — 2004
Extremal point queries with lines and line segments and related problemsOvidiu Daescu, Robert Serfling — 2005
A space-optimal data-stream algorithm for coresets in the planePankaj K. Agarwal, Hai Yu — 2007
Robust Shape Fitting via Peeling and Grating CoresetsPankaj K. Agarwal, Sariel Har-Peled, Hai Yu — 2006
On approximating the depth and related problemsBoris Aronov, Sariel Har-Peled — 2005
Practical Methods for Shape Fitting and Kinetic Data Structures using CoresetsHai Yu, Pankaj K. Agarwal, Raghunath Poreddy — 2004
Faster core-set constructions and data stream algorithms in fixed dimensionsTimothy M. Chan — 2004
Streaming 1-Center with Outliers in High DimensionsHamid Zarrabi-Zadeh, Asish Mukhopadhyay — 2009
The weighted-volume derivative of a space-filling diagramHerbert Edelsbrunner, Patrice Koehl — 2003
Generalized Core Vector MachinesIvor W. Tsang, James T. Kwok, Jacek Zurada — 2006

Shape fitting with outliers

Summary

Keywords

References

Cited by

Related papers