非表示:
キーワード:
-
要旨:
We consider the problem of computing a representation of the plane graph
induced by one (or more) algebraic curves in the real plane. We make no
assumptions about the curves, in particular we allow arbitrary singularities
and arbitrary intersection. This problem has been well studied for the case of
a single curve. All proposed approaches to this problem so far require finding
and counting real roots of polynomials over an algebraic extension of Q, i.e.
the coefficients of those polynomials are algebraic numbers. Various algebraic
approaches for this real root finding and counting problem have been developed,
but they tend to be costly unless speedups via floating point approximations
are introduced, which without additional checks in some cases can render the
approach incorrect for some inputs.We propose a method that is always correct
and that avoids finding and counting real roots of polynomials with
non-rational coefficients. We achieve this using two simple geometric
approaches: a triple projections method and a curve avoidance method. We have
implemented our approach for the case of computing the topology of a single
real algebraic curve. Even this prototypical implementation without
optimizations appears to be competitive with other implementations.
