Shape fitting with outliers

Sariel Har-Peled, Yusu Wang

Research output: Contribution to conferencePaperpeer-review


Given a set H of n hyperplanes in ℝ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 subset of H of size O(k/ε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.

Original languageEnglish (US)
Number of pages10
StatePublished - 2003
EventNineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States
Duration: Jun 8 2003Jun 10 2003


OtherNineteenth Annual Symposium on Computational Geometry
Country/TerritoryUnited States
Citysan Diego, CA


  • Approximation
  • Outliers
  • Shape fitting

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Shape fitting with outliers'. Together they form a unique fingerprint.

Cite this