Abstract: Since it is difficult to compute the minimum distance between two algebraic curves by traditional methods when the expressions of the algebraic curves are complicated, a subdivision algorithm is proposed. Quadtree data structure was used to subdivide the two algebraic curves into two sets of pixels. Interval arithmetic was used to compute the minimum distance interval between these two sets of pixels. The center of this interval is the approximation of the minimum distance between the two algebraic curves. The error is less than a half of this interval. Compared with traditional methods, this method can obtain the approximation of the minimum distance between two algebraic curves at any precision, as well as the error estimation at the same time.

Key words: algebraic curve, minimum distance, interval arithmetic, subdivision algorithm