Full Text:   <1647>

CLC number: TP391.72

On-line Access: 

Received: 2008-07-16

Revision Accepted: 2008-08-20

Crosschecked: 2008-10-27

Cited: 0

Clicked: 3074

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

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

10.1631/jzus.A08GMP01


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",
volume="9",
number="12",
pages="1685~1693",
year="2008",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.A08GMP01"
}

%0 Journal Article
%T Computing the topology of an arrangement of implicitly defined real algebraic plane curves
%A Jorge CARAVANTES
%A Laureano GONZALEZ-VEGA
%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

TY - JOUR
T1 - Computing the topology of an arrangement of implicitly defined real algebraic plane curves
A1 - Jorge CARAVANTES
A1 - Laureano GONZALEZ-VEGA
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


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.

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

Reference

[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

<1>

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