Algorithms for Vertical and Orthogonal L1 Linear Approximation of Points
<italic>This paper presents algorithms for approximating a set of n points by a linear function, or a line, that minimizes the L<subscrpt>1</subscrpt> 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</italic> [9], <italic>although &Ogr;(n<supscrpt>3</supscrpt>) naive algorithms can be easily obtained based on some simple characteristics of optimal L<subscrpt>1</subscrpt> solutions. In this paper, an &Ogr;(n) optimal time algorithm for the weighted vertical L<subscrpt>1</subscrpt> 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 &Ogr;(n<supscrpt>1.5</supscrpt></italic> log<supscrpt>2</supscrpt> <italic>n) algorithm is presented for the unweighted orthogonal problem, and an &Ogr;(n<supscrpt>2</supscrpt>) algorithm is presented for the weighted problem. An</italic> &OHgr;(<italic>n</italic> log <italic>n) lower bound for the orthogonal L<subscrpt>1</subscrpt> problem is shown under a certain model of computation. Also, the complexity of solving the orthogonal L<subscrpt>1</subscrpt> problem is related to the construction of the k-belt of an arrangement of lines.</italic>