Computing the Topology of an Arrangement of Implicit and Parametric Curves Given by Values

详细信息    查看全文

• 作者：Jorge Caravantes (19)
  Mario Fioravanti (20)
  Laureano Gonzalez鈥揤ega (20)
  Ioana Necula (21)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8660
• 期：1
• 页码：59-73
• 全文大小：718 KB
• 参考文献：1. Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol.聽10. Springer (1987)
  2. Edelsbrunner, H., O鈥橰ourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput.聽15, 341鈥?63 (1986) CrossRef
  3. Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 49鈥?19. Elsevier (2000)
  4. Berberich, E., Eigenwillig, A., Hemmer, M., Hert, S., Mehlhorn, K., Sch枚mer, E.: A computational basis for conic arcs and boolean operations on conic polygons. In: M枚hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.聽2461, pp. 174鈥?86. Springer, Heidelberg (2002) CrossRef
  5. Wein, R.: High-level filtering for arrangements of conic arcs. In: M枚hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.聽2461, pp. 884鈥?95. Springer, Heidelberg (2002) CrossRef
  6. Eigenwillig, A., Kettner, L., Sch枚mer, E., Wolpert, N.: Exact, efficient and complete arrangement computation for cubic curves. Computational Geometry聽35, 36鈥?3 (2006) CrossRef
  7. Caravantes, J., Gonzalez-Vega, L.: Improving the topology computation of an arrangement of cubics. Computational Geometry聽41, 206鈥?18 (2008) CrossRef
  8. Caravantes, J., Gonzalez-Vega, L.: Computing the topology of an arrangement of quartics. In: Martin, R., Sabin, M.A., Winkler, J.R. (eds.) Mathematics of Surfaces 2007. LNCS, vol.聽4647, pp. 104鈥?20. Springer, Heidelberg (2007) CrossRef
  9. Wolpert, N.: Jacobi curves: Computing the exact topology of arrangements of non-singular algebraic curves. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.聽2832, pp. 532鈥?43. Springer, Heidelberg (2003) CrossRef
  10. Plantinga, S., Vegter, G.: Isotopic approximation of implicit curves and surfaces. In: Boissonnat, J.D., Alliez, P. (eds.) Symposium on Geometry Processing. ACM International Conference Proceeding Series, vol.聽71, pp. 245鈥?54. Eurographics Association (2004)
  11. Hijazi, Y., Breuel, T.: Computing arrangements using subdivision and interval arithmetic. In: Chenin, P., Lyche, T., Schumaker, L. (eds.) Curve and Surface Design: Avignon 2006, pp. 173鈥?82. Nashboro Press (2007)
  12. Alberti, L., Mourrain, B., Wintz, J.: Topology and arrangement computation of semi-algebraic planar curves. Computer Aided Geometric Design聽25(8), 631鈥?51 (2008) CrossRef
  13. Mourrain, B., Wintz, J.: A subdivision method for arrangement computation of semi-algebraic curves. In: Emiris, I.Z., Sottile, F., Theobald, T. (eds.) Nonlinear Computational Geometry. The IMA Volumes in Mathematics and its Applications, vol.聽151, pp. 165鈥?88. Springer (2010)
  14. Eigenwillig, A., Kerber, M.: Exact and efficient 2d-arrangements of arbitrary algebraic curves. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 122鈥?31. SIAM (2008)
  15. Berberich, E., Emeliyanenko, P., Kobel, A., Sagraloff, M.: Exact symbolic-numeric computation of planar algebraic curves. Theoretical Computer Science聽491, 1鈥?2 (2013) CrossRef
  16. Shakoori, A.: Bivariate Polynomial Solver by Values. PhD thesis, The University of Western Ontario (2007)
  17. Hermann, T.: On the stability of polynomial transformations between Taylor, B茅zier, and Hermite forms. Numerical Algorithms聽13, 307鈥?20 (1996) CrossRef
  18. Berrut, J., Trefethen, L.: Barycentric Lagrange interpolation. SIAM Review聽46(3), 501鈥?17 (2004) CrossRef
  19. Higham, N.J.: The numerical stability of barycentric Lagrange interpolation. IMA Journal of Numerical Analysis聽24, 547鈥?56 (2004) CrossRef
  20. Demmel, J.W.: Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia (1997) CrossRef
  21. Corless, R., Diaz-Toca, G., Fioravanti, M., Gonzalez-Vega, L., Rua, I., Shakoori, A.: Computing the topology of a real algebraic plane curve whose defining equations are available only 鈥渂y values鈥? Comput. Aided Geom. Des.聽30(7), 675鈥?06 (2013) CrossRef
  22. Helmke, U., Fuhrmann, P.A.: Bezoutians. Linear Algebra and Its Applications 122/123/124, 1039鈥?097 (1989)
  23. Bini, D., Pan, V.: Polynomial and Matrix Computations. Birkh盲user (1994)
  24. Heinig, G., Rost, K.: Algebraic methods for Toeplitz-like matrices and operators. Operator Theory: Advances and Applications聽13 (1984)
  25. Corless, R.M.: On a Generalized Companion Matrix Pencil for Matrix Polynomials Expressed in the Lagrange basis. In: Symbolic-Numeric Computation, pp. 1鈥?8. Birkh盲user (2006)
  26. Corless, R., Gonzalez-Vega, L., Necula, I., Shakoori, A.: Topology determination of implicitly defined real algebraic plane curves. In: Proceedings of the 5th International Workshop on Symbolic and Numeric Algorithms for Scientific Computing SYNASC 2003, Universitatea din Timisoara. Analele Universitatii din Timisoara, Matematica - Informatica, vol.聽XLI, pp. 78鈥?0 (2003)
  27. Eigenwillig, A., Kerber, M., Wolpert, N.: Fast and exact geometric analysis of real algebraic plane curves. In: Proceedings ISSAC 2007 (July 2007)
  28. Alcazar, J., Diaz-Toca, G.: Topology of 2d and 3d rational curves. Comput. Aided Geom. Des.聽27, 483鈥?02 (2010) CrossRef
  
• 作者单位：Jorge Caravantes (19)
  Mario Fioravanti (20)
  Laureano Gonzalez鈥揤ega (20)
  Ioana Necula (21)
  
  19. Universidad Complutense de Madrid, Spain
  20. Universidad de Cantabria, Spain
  21. Universidad de Sevilla, Spain
  
• ISSN：1611-3349

文摘

Curve arrangement studying is a subject of great interest in Computational Geometry and CAGD. In our paper, a new method for computing the topology of an arrangement of algebraic plane curves, defined by implicit and parametric equations, is presented. The polynomials appearing in the equations are given in the Lagrange basis, with respect to a suitable set of nodes. Our method is of sweep-line class, and its novelty consists in applying algebra by values for solving systems of two bivariate polynomial equations. Moreover, at our best knowledge, previous works on arrangements of curves consider only implicitly defined curves.