ISSN:
1432-0541
Keywords:
Computational geometry
;
Modified pruning technique
;
LinearL 1 approximation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper we present a linear-time algorithm for approximating a set ofn points by a linear function, or a line, that minimizes theL 1 norm. The algorithmic complexity of this problem appears not to have been investigated, although anO(n 3) naive algorithm can be easily obtained based on some simple characteristics of an optimumL 1 solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linearL 1 approximation of many points in practice. The complexity ofL 1 linear approximation of a piecewise linear function is also touched upon.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01553880
Permalink
