Access Restriction

Author O'Rourke, Joseph
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Computational geometry ♦ Incremental algorithms ♦ Piecewise linear approximation ♦ Half-plane intersection ♦ Computational complexity ♦ On-line algorithms
Abstract Applications often require fitting straight lines to data that is input incrementally. The case where a data range [αk, ωk] is received at each tk, t1 < t2 < … tn, is considered. An algorithm is presented that finds all the straight lines u = mt + b that pierce each data range, i.e., all pairs (m, b) such that αk ≤ mtk + b ≤ ωk for k = 1, … , n. It may be that no single line fits all the ranges, and different alternatives for handling this possibility are considered. The algorithm is on-line, producing the correct partial result after processing the first k ranges for all k < n. For each k, the set of (m, b) pairs constitutes a convex polygon in the m-b parameter space, which can be constructed as the intersection of 2k half-planes. It is shown that the O(n logn) half-plane intersection algorithm of Shamos and Hoey can be improved in this special case to O(n).
Description Affiliation: John Hopkins Univ., Baltimore, MD (O'Rourke, Joseph)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 24
Issue Number 9
Page Count 5
Starting Page 574
Ending Page 578

Open content in new tab

   Open content in new tab
Source: ACM Digital Library