平面代数曲线的交点隔离算法

判断两条平面代数曲线在给定区域内是否相交是几何设计的一个基本问题.针对代数曲线的正规交点,本文建立了一个隔离算法.首先使用结式计算和单变元多项式的实根隔离算法,获得一系列初始矩形Box.这些Box中要么没有交点,要么只有唯一交点.通过引入伴随多项式,建立了判定给定Box中无交点和有唯一正规交点的方法 .利用Maple平台实现了隔离代数曲线正规交点的算法Real Intersection.经过随机方程组实验,该方法在高次数的情况明显优于Maple中基于有理单变元表示的交点隔离方法 Isolate.

An algorithm for isolating the intersection points of two plane algebraic curves

One of the basic problems of geometric design is to determine the intersection points of two planar algebraic curves within a given area. This paper establishes an isolation algorithm in order to solve the above problem. The algorithm firstly uses the resultant computation and the real roots isolating algorithm of univariate polynomials to get a series of initial rectangular boxes. In each initial box, there exists no intersection point or only one intersection point. Then the ad-joint polynomial is introduced to determine whether there is no intersection or only one normal intersection over every box. The research has implemented an algorithm named RealIntersection with Maple 18. By comparing RealIntersection with the bi-variate version of Isolate (based on rational univariate representation), it is found that this approach is better than Isolate when the degree of variables is higher.