Shape Fitting with Outliers

Sariel Har-Peled and Yusu Wang

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

Journal version: Postscript, PDF.

@string{SOCG_2003 = "Proc. 19th Annu. ACM Sympos. Comput. Geom."}

@InProceedings{hw-sfo-03,
  author =       {S. {Har-Peled} and Y. Wang},
  title =        {Shape Fitting with Outliers},
  booktitle =    SOCG_2003,
  pages =        {29--38},
  url =          {http://www.uiuc.edu/~sariel/research/papers/02/outliers/}
  year =         2002
}

Last modified: Thu Jun 12 16:34:11 CDT 2003