标题： 实代数曲线上的连通性查询算法 显示英文标题

标题： Algorithm for connectivity queries on real algebraic curves

摘要： 我们考虑回答实代数曲线上的连通性查询问题。该曲线作为代数曲线的实轨迹给出，假设其处于一般位置，并由某些有理参数化定义。查询点由零维参数化给出。我们设计了一个算法，可以在时间上与$N^6$成对数线性关系来计算所研究实曲线的连通分支数量，并判断哪个查询点位于哪个连通分支中，其中$N$是输入多项式的次数和系数位大小的最大值。这与目前计算实平面曲线拓扑的最佳已知界限相匹配。该算法的主要创新之处在于避免了计算曲线的完整拓扑。 显示英文摘要

摘要： We consider the problem of answering connectivity queries on a real algebraic curve. The curve is given as the real trace of an algebraic curve, assumed to be in generic position, and being defined by some rational parametrizations. The query points are given by a zero-dimensional parametrization. We design an algorithm which counts the number of connected components of the real curve under study, and decides which query point lie in which connected component, in time log-linear in $N^6$, where $N$ is the maximum of the degrees and coefficient bit-sizes of the polynomials given as input. This matches the currently best-known bound for computing the topology of real plane curves. The main novelty of this algorithm is the avoidance of the computation of the complete topology of the curve.