Similar articles

Abstract: We introduce a new algebraic approach dealing with the problem of computing the topology of an arrangement of a finite set of real algebraic plane curves presented implicitly. The main achievement of the presented method is a complete avoidance of irrational numbers that appear when using the sweeping method in the classical way for solving the problem at hand. Therefore, it is worth mentioning that the efficiency of the proposed method is only assured for low-degree curves.

[1] Basu, S., Pollack, R., Roy, M.F., 2006. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, Vol. 10. Springer.

[2] Berberich, E., Eigenwillig, A., Hemmer, M., Hert, S., Mehlhorn, K., Schömer, E., 2002. A computational basis for conic arcs and Boolean operations on conic polygons. LNCS, 2461:174-186.

[3] Caravantes, J., Gonzalez-Vega, L., 2007a. Computing the topology of an arrangement of quartics. LNCS, 4647:104-120.

[4] Caravantes, J., Gonzalez-Vega, L., 2007b. Improving the topology computation of an arrangement of cubics. Comput. Geometr.: Theory Appl., 41(3):206-218.

[5] Cheng, J.S., Lazard, S., Penaranda, L., Pouget, M., Rouillier, F., Tsigaridas, E., 2008. On the Topology of Planar Algebraic Curves. Proc. 24th European Workshop on Computational Geometry, p.213-216.

[6] Eigenwillig, A., Kettner, L., Schömer, E., Wolpert, N., 2006. Exact, efficient and complete arrangement computation for cubic curves. Comput. Geometr., 35(1-2):36-73.

[7] Eigenwillig, A., Kerber, M., Wolpert, N., 2007. Fast and Exact Geometric Analysis of Real Algebraic Plane Curves. Proc. Int. Symp. on Symbolic and Algebraic Computation. ACM Press, p.151-158.

[8] Flato, E., Halperin, D., Hanniel, I., Nechushtan, O., Ezra, E., 2000. The design and implementation of planar maps in CGAL. ACM J. Exp. Algor., 5:1-23

[9] Gonzalez-Vega, L., El Kahoui, M., 1996. An improved upper complexity bound for the topology computation of a real algebraic plane curve. J. Compl., 12(4):527-544.

[10] Gonzalez-Vega, L., Necula, I., 2002. Efficient topology determination of implicitly defined algebraic plane curves. Comput. Aided Geometr. Des., 19(9):719-743.

[11] Hong, H., 1996. An efficient method for analyzing the topology of plane real algebraic curves. Math. Comput. Simul., 42(4-6):571-582.

[12] Li, Y.B., 2006. A new approach for constructing subresultants. Appl. Math. Comput., 183:471-476.

[13] Liang, C., Mourrain, B., Pavone, J.P., 2007. Subdivision methods for the topology of 2D and 3D implicit curves. Geometr. Model. Algebr. Geometr., p.199-214.

[14] Mehlhorn, K., Noher, S., 1999. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press.

[15] Sakkalis, T., 1991. The topological configuration of a real algebraic curve. Bull. Aust. Math. Soc., 43:37-50.

[16] Sakkalis, T., Farouki, R., 1990. Singular points of algebraic curves. J. Symb. Comput., 9(4):405-421.

[17] Seel, M., 2001. Implementation of Planar Nef Polyhedra. Report MPI-I-2001-1-003, Max-Planck-Institut für Informatik.

[18] Seidel, R., Wolpert, N., 2005. On the Exact Computation of the Topology of Real Algebraic Curves (Exploiting a Little More Geometry and a Little Less Algebra). Proc. 21st Annual ACM Symp. on Computational Geometry. ACM Press, p.107-115.

[19] Wein, R., 2002. High-level filtering for arrangements of conic arcs. LNCS, 2461:884-895.