English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 &Ogr;(n3) naive algorithms can be easily obtained based on some simple characteristics of optimal L1 solutions. In this paper, an &Ogr;(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 &Ogr;(n1.5 log2 n) algorithm is presented for the unweighted orthogonal problem, and an &Ogr;(n2) algorithm is presented for the weighted problem. An &OHgr;(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.

Algorithms for vertical and orthogonal L1 linear approximation of points