

1. Introduction
In this project an online O(n) algorithm proposed by Joseph O'Rourke [1]
for fitting straight lines to incremental data ranges
is examined.
 Basic Idea
We consider data ranges [a_{k},w_{k}] which are
received at each time t_{k} sequentially. Then, the set
of all straight lines u = mt + b that fits the (t_{k},
[a_{k},w_{k}]), k= 1,2,...,n
can be represented as the set of all (m,b) pairs that satisfy
the equations
 a_{k} < mt_{k}
+ b < w_{k} for k = 1,...n
(1)
Figure 1. Example of tb parameter space
 By changing our point of view from the ut parameter
space where the data live to the mb space, we can consider the
inequality (1) as the constraint equations of a linear
programming problem of two variables m and b.
b > (t_{k})m + a_{k}
b < (t_{k})m + w_{k}
(2)
 Thus, the original problem of finding straight lines of n
data ranges can be reduced to finding the intersection P_{n}
of feasible regions P_{k} (or intersections of halfplanes),
k = 1,...,n constrained by the 2n parallel equations in (2).
Figure 2. Example of mb parameter space (representation of the
first five data ranges of Figure 1.)
 Goal
Construct a convex polygon P_{k}
from P_{k1} online in the mb parameter space using the
set of sequential inputs (t_{k}, [a_{k},w_{k}]).
2. Polygon
Properties
Before we mention the algorithm it is necessary to go over the
basic properties of polygons which are used in the algorithm.
It is assumed that t_{k} > 0 and t_{k} <
t_{k+1} for all k.
 Lemma 1. Each
edge of each polygon P_{k} in mb parameter space has
a strictly negative slope.
Proof. Polygon
P_{k} is the intersection of 2k halfplanes, and so each
edge of P_{k} lies along one of the 2k halfplane edges.
Each halfplane is described by one of the forms displayed as
(2). Therefore, each plane edge has a slope of t_{i}.
Since t_{i} > 0 and t_{i} < t_{k}
for 1 < i < k by the assumption, each slope lies
within [t_{k}, 0].
 Definition 1. Define
mmax, bmax, mmin and bmin as the following.
 mmax_{k}=max{m:(m,b)
is a vertex of P_{k}}
bmax_{k}=max{b:(m,b) is a vertex of P_{k}}
mmin_{k}=min{m:(m,b) is a vertex of P_{k}}
bmin_{k}=min{b:(m,b) is a vertex of P_{k}}
 Lemma 2. For
each polygon P_{k} in mb parameter space, the rightmost
point of the polygon is also the lowest point, and the leftmost
point is also the highest point.
Proof. Suppose
that the rightmost and the lowest points are distinct. Then there
exist m' and b' such that m' < mmax_{k} and b' >
bmin_{k} and (mmax_{k}, b') and (m', bmin_{k})
are both vertices of P_{k}. It is not possible to close
off P_{k} by connecting the rightmost and lowest vertices
without adding at least one edge of positive slope. This contradicts
Lemma 1. The assumption of the leftmost and highest points being
distinct gives rise to the same contradiction.
 Definition 2.The
leftmost point L_{k} is defined by (mmax_{k},bmax_{k})
and rightmost point R_{k} is defined by (mmin_{k},bmin_{k}).
 Definition 3. The
upper halfpolygonal chain C_{u} is defined by {v_{k}:
v_{k} is a vertex of P_{k} which lies between
R_{k} and L_{k} counterclockwise order}. The
lower halfpolygonal chain C_{l} is defined by {v_{k}:
v_{k} is a vertex of P_{k} which lies between
R_{k} and L_{k} clockwise order}.
3. Algorithm
 Input:
(t_{k}, a_{k}, w_{k}), i=1,...,n
Computed: Polygons
P_{1}, P_{2},...,P_{n}
Step 1. Compute
P_{2} and initialize L_{2} and R_{2}
Step 2. Repeat
from k=3 to n
 Step 21. If
R_{k1} is to the left of the halfplane b >
(t_{k})m + a_{k} or L_{k1} is to the
right of the halfplane b < (t_{k})m + w_{k}
then there is no straight line fitting data range at t_{k}.
Thus, reinitialize the process by setting P_{k} to the
quadrilateral formed from the data ranges at t_{k1}
and t_{k}. Initialize L_{k} and R_{k}.
Step 22. Else
 Step 221. Search
for the two intersection points of the halfplane b <
(t_{k})m + a_{k} with P_{k1}
 (a) If
R_{k1} is inside of the halfplane, go to Step 222.
(b) Find
intersection point with edges of C_{u} counterclockwisely.
(c) Find
intersection point with edges of C_{l} clockwisely.
(d) Set
the lowest intersection point as R_{k}
 Step 222. Search
for the two intersection points of the halfplane b >
(t_{k})m + w_{k} with P_{k1}
 (a) If
L_{k1} is inside of the halfplane, go to Step 223.
(b) Find
intersection point with edges of C_{u} clockwisely.
(c) Find
intersection point with edges of C_{l} counterclockwisely.
(d) Set
the highest intersection point as L_{k}
 Step 223. Remove
all vertices outside of the two intersection halfplanes from
P_{k1}. Add in the new intersecting vertices.
Figure 3. Example of constructing P_{k} from P_{k1}
online
4. Correctness of Algorithm
To show that the algorithm computes P_{k} intersections
correctly, we need to show the following.
 (1) Each
halfplane edge either does not intersect the polygon at all
or intersects C_{u} once and C_{l} once.
 (2)The
algorithm correctly computes the intersection points.
The proof of (2) follows if (1) is proved to be true because
of the design of the algorithm.
Proof of (1). From Lemma
1, all the edges of P_{k1} have slopes in the range
[t_{k1}, 0). Since t_{k} > t_{k1},
the halfplane edge is steeper than any of the polygon edges.
This implies that the halfplane edge intersects C_{u}
and C_{l} exactly once and it enters the polygon if the
intersection points are not L_{k1} or R_{k1}.
Figure 4 illustrates two impossible cases.
Figure 4. Impossible cases of intersecting the halfplane and
P_{k1}
5. Java Applet
6. References
 [1] O'Rourke, J., An OnLine Algorithm for Fitting Straight
Lines Between Data Ranges, Comm. ACM, 24, 9, 574578, 1981.
[2] Freedman, A.M., Buneman, O.P., Peckham, G., and Trattner,
A., Automatic Recognition of Significant Events in the Vital
Signs of Neonatal Infants. Compu. Biomed. Res. 12, 2, 141148,
1979.
[3] Lee, D.T. and Preparata, F.P., An Optimal Algorithm for Finding
the Kernel of a Polygon. J. ACM 26, 3, 415421, 1979.
[4] O'Rourke, J., and Badier, N., Modelbased Image Analysis
of Human and Motion using Constraint Propagation, IEEE Trans.
on Pattern Analysis and Machine Intelligence, PAMI2, 6, 522536,
1980.
[5] Pavlidis, T., Structural Pattern Recognition. SpringerVerlag,
Berlin, 168184, 1977.
[6] Preparata, F.P., An Optimal Realtime Algorithm for Plannar
Convex Hulls. Comm. ACM, 22,7, 402405, 1979.
[7] Shamos, M.I., and Hoey, D., Geometric Intersection Problems,
17th Ann. IEEE Symp. Foundations of Computer Science, 208215,
1976.
[8] Shamos, M.I., Computational Geometry, PhD Dissertation, Yale
University, 1978.
