On Sorting Points along a Real Algebraic Curve

概要

論文の詳細を見る
In this paper we use the Cylindrical Algebraic Decomposition (CAD) method to develop algorithms for sorting points along a real algebraic curve. Our approach has less computational complexity than the convex decomposition approach propose by Johnstone and Bajaj [1]. To sort m points along a real algebraic curve of degree n, the convex decomposition approach costs O(mn_3β[n] +mlogm) time, whereβ[n] is the cost of finding the real roots of an algebraic equation of order n. In contrast, our approach costs O(mn_2+mα[n] +m log m) time, where α[n] is the cost of computing the number of real roots of an order n algebraic equation on a certain interval, which is obviously no more expensive thanβ[n]. We also explore the cyclic structure of real algebraic curves: we show how a curve can be naturally decomposed into a finite number of closed cycles and open chains, and claim that this number is no larger than the genus plus the degree of the curve.
一般社団法人情報処理学会の論文
1992-11-30