How to get close to the median shape

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we study the problem of Li-fitting a shape to a set of n points in ℝd (where d is a fixed constant), where the target is to minimize the sum of distances of the points to the shape, or alternatively the sum of squared distances. We present a general technique for computing a (1+ε)-approximation for such a problem, with running time O(n + poly(log n, 1/ε)), where poly(log n, 1/ε) is a polynomial of constant degree of log n and 1/ε (the power of the polynomial is a function of d). This is a linear time algorithm for a fixed ε > 0, and is the first subquadratic algorithm for this problem. Applications of the algorithm include best fitting either a circle, a sphere or a cylinder to a set of points when minimizing the sum of distances (or squared distances) to the respective shape.

Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PublisherAssociation for Computing Machinery (ACM)
Pages402-410
Number of pages9
ISBN (Print)1595933409, 9781595933409
DOIs
StatePublished - 2006
Event22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States
Duration: Jun 5 2006Jun 7 2006

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
Volume2006

Other

Other22nd Annual Symposium on Computational Geometry 2006, SCG'06
CountryUnited States
CitySedona, AZ
Period6/5/066/7/06

Keywords

  • Approximation
  • Shape fitting

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'How to get close to the median shape'. Together they form a unique fingerprint.

Cite this