Algorithms for vertical and orthogonal L1 linear approximation of points
Peter Yamamoto, Kenji Kato, Kenichiro Imai, Hiroshi Imai · 1988
This paper presents algorithms for approximating a set of n points by a linear function, or a line, that minimizes the L1 norm of vertical and orthogonal distances. The algorithms find exact solutions based upon geometric properties of the problems as opposed to approximate solutions based upon existing numerical techniques. The algorithmic complexity of these problems appears not to have been investigated before our work in [9], although Ο(n3) naive algorithms can be easily obtained based on some simple characteristics of optimal L1 solutions. In this paper, an Ο(n) optimal time algorithm for the weighted vertical L1 problem is presented. The algorithm is based upon a modified multi-dimensional search technique which extends the applicability of the basic technique to a wider class of problems. An Ο(n1.5 log2 n) algorithm is presented for the unweighted orthogonal problem, and an Ο(n2) algorithm is presented for the weighted problem. An Ω(n log n) lower bound for the orthogonal L1 problem is shown under a certain model of computation. Also, the complexity of solving the orthogonal L1 problem is related to the construction of the k-belt of an arrangement of lines.