How to get close to the median shape

Research output: Contribution to journalArticle

Abstract

In this paper, we study the problem of L1-fitting a shape to a set of n points in R 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(logn,1/)), where poly(logn,1/) is a polynomial of constant degree of logn 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)
Pages (from-to)39-51
Number of pages13
JournalComputational Geometry: Theory and Applications
Volume36
Issue number1
DOIs
StatePublished - Jan 1 2007

    Fingerprint

Keywords

  • Approximation algorithms
  • Shape fitting

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Cite this