Given m points in the plane and a threshold t, a curve is defined to b
e robust if at least t points lie on it. Efficient algorithms for dete
cting robust curves are given; the key contribution is to use randomiz
ed sampling. In addition, an approximate version of the problem is int
roduced. A geometric solution to this problem is given; it too can be
enhanced by randomization. These algorithms are readily generalized to
solve the problem of robust curve detection in a scene of curve fragm
ents: given a set of curve segments, a curve sigma is defined to be ro
bust if curve segments of total length at least 1 lie on sigma. Again,
both an exact and an approximate version of the problem are considere
d. The problems and solutions are closely related to the well-investig
ated Hough transform technique. (C) 1994 Academic Press, Inc.