Full Text:   <1682>

CLC number: TP391.72

On-line Access: 

Received: 2008-07-16

Revision Accepted: 2008-08-20

Crosschecked: 2008-10-27

Cited: 0

Clicked: 3185

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

Journal of Zhejiang University SCIENCE A 2008 Vol.9 No.12 P.1685~1693


Computing the topology of an arrangement of implicitly defined real algebraic plane curves

Author(s):  Jorge CARAVANTES, Laureano GONZALEZ-VEGA

Affiliation(s):  Department of Mathematics, Statistics and Computation, University of Cantabria, Santander, 39005, Cantabria, Spain

Corresponding email(s):   jorge.caravantes@unican.es, laureano.gonzalez@unican.es

Key Words:  Topology computation, Real plane curves, Sweeping method

Jorge CARAVANTES, Laureano GONZALEZ-VEGA. Computing the topology of an arrangement of implicitly defined real algebraic plane curves[J]. Journal of Zhejiang University Science A, 2008, 9(12): 1685~1693.

@article{title="Computing the topology of an arrangement of implicitly defined real algebraic plane curves",
author="Jorge CARAVANTES, Laureano GONZALEZ-VEGA",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Computing the topology of an arrangement of implicitly defined real algebraic plane curves
%J Journal of Zhejiang University SCIENCE A
%V 9
%N 12
%P 1685~1693
%@ 1673-565X
%D 2008
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A08GMP01

T1 - Computing the topology of an arrangement of implicitly defined real algebraic plane curves
J0 - Journal of Zhejiang University Science A
VL - 9
IS - 12
SP - 1685
EP - 1693
%@ 1673-565X
Y1 - 2008
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A08GMP01

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[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.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE