CLC number: TP391.72
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2008-10-27
Cited: 0
Clicked: 4978
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.
[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>