非表示:
キーワード:
-
要旨:
We present a certified and complete algorithm to compute arrangements of real
planar algebraic curves. It computes the decomposition of the plane induced by
a finite number of algebraic curves in terms of a cylindrical algebraic
decomposition. From a high-level perspective, the overall method splits into
two main subroutines, namely an algorithm denoted BiSolve to isolate the real
solutions of a zero-dimensional bivariate system, and an algorithm denoted
GeoTop to compute the topology of a single algebraic curve.
Compared to existing approaches based on elimination techniques, we
considerably improve the corresponding lifting steps in both subroutines. As a
result, generic position of the input system is never assumed, and thus our
algorithm never demands for any change of coordinates. In addition, we
significantly limit the types of symbolic operations involved, that is, we only
use resultant and gcd computations as purely symbolic operations. The latter
results are achieved by combining techniques from different fields such as
(modular) symbolic computation, numerical analysis and algebraic geometry.
We have implemented our algorithms as prototypical contributions to the
C++-project CGAL. We exploit graphics hardware to expedite the remaining
symbolic computations. We have also compared our implementation with the
current reference implementations, that is, LGP and Maple�s Isolate for
polynomial system solving, and CGAL�s bivariate algebraic kernel for analyses
and arrangement computations of algebraic curves. For various series of
challenging instances, our exhaustive experiments show that the new
implementations outperform the existing ones.
