Shape fitting with outliers

ABSTRACT

Given a set H of n hyperplanes in R^d, we present an algorithm that e-approximates the extent between the top and bottom k levels of the arrangement of H in time O(n + (k/e)^c), where c is a constant depending on d. The algorithm relies on computing a subset of H of size.O(k/e^d-1), in near linear time, such that the k-level of the arrangement of the subset approximates that of the original arrangement. Using this algorithm, we propose efficient approximation algorithms for shape fitting with outliers for various shapes. This is the first algorithms to handle outliers efficiently for the shape fitting problems considered.

REFERENCES

• 1: P. K. Agarwal, B. Aronov, S. Har-Peled, and M. Sharir. Approximation and exact algorithms for minimum-width annuli and shells. Discrete Comput. Geom., 24(4):687--705, 2000.
• 2: Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications, SIAM Journal on Computing, v.29 n.3, p.912-953, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539795295936]
• 3: Pankaj K. Agarwal , Sariel Hal-Peled, Maintaining approximate extent measures of moving points, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 07-09, 2001, Washington, D.C., United States
• 4: P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. http://valis.cs.uiuc.edu/~sariel/research/papers/01/fitting/, 2002.
• 5: P. K. Agarwal and J. Matouaek. On range searching with semialgebraic sets. Discrete Comput. Geom., 11:393--418, 1994.
• 6: N. Alon and J. H. Spencer. The probabilistic method. Wiley Inter-Science, 2nd edition, 2000.
• 7: Gill Barequet , Sariel Har-Peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, Journal of Algorithms, v.38 n.1, p.91-109, Jan. 2001 [doi>10.1006/jagm.2000.1127]
• 8: Timothy M. Chan, Low-Dimensional Linear Programming with Violations, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.570, November 16-19, 2002
• 9: Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
• 10: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 11: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 12: Amitava Datta , Hans-Peter Lenhof , Christian Schwarz , Michiel Smid, Static and dynamic algorithms for k-point clustering problems, Journal of Algorithms, v.19 n.3, p.474-503, Nov. 1995 [doi>10.1006/jagm.1995.1048]
• 13: John Dunagan , Santosh Vempala, Optimal outlier removal in high-dimensional, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.627-636, July 2001, Hersonissos, Greece [doi>10.1145/380752.380860]
• 14: D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes. Discrete Comput. Geom., 11:321--350, 1994.
• 15: Jeff Erickson, New Lower Bounds for Convex Hull Problems in Odd Dimensions, SIAM Journal on Computing, v.28 n.4, p.1198-1214, Aug. 1999 [doi>10.1137/S0097539797315410]
• 16: J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies. Discrete Comput. Geom., 13:41--57, 1995.
• 17: J. Gao and L. J. Guibas. Staying in the middle: approximate medians in R1 and R2 for moving points. menuscript, 2002.
• 18: S. Har-Peled, Approximate Shape Fitting via Linearization, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.66, October 14-17, 2001
• 19: S. Har-Peled and Y. Wang. Shape fitting with outliers. http://ww.uiuc.edu/~sariel/research/papers/02/outliers/, 2002.
• 20: Jiří Matoušek, On enclosing k points by a circle, Information Processing Letters, v.53 n.4, p.217-221, Feb. 24, 1995 [doi>10.1016/0020-0190(94)00190-A]
• 21: J. Matousek. On geometric optimization with few violated constraints. Discrete Comput. Geom., 14:365--384, 1995.
• 22: J. Matousek. On constants for cuttings in the plane. Discrete Comput. Geom., 20:427--448, 1998.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Theory

Keywords:
approximation, outliers, shape fitting