More Web Proxy on the site http://driver.im/

research-article

On the geometry and the topology of parametric curves

Authors:

Christina Katsamaki,

Fabrice Rouillier,

Elias Tsigaridas,

Zafeirakis ZafeirakopoulosAuthors Info & Claims

ISSAC '20: Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation

Pages 281 - 288

https://doi.org/10.1145/3373207.3404062

Published: 27 July 2020 Publication History

Abstract

We consider the problem of computing the topology and describing the geometry of a parametric curve in R^n. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our method exploits the benefits of the parametric representation and does not resort to implicitization.

Most importantly, we perform all computations in the parameter space and not in the implicit space. When the parametrization involves polynomials of degree at most d and maximum bitsize of coefficients τ, then the worst case bit complexity of PTOPO is Õ_B (nd⁶ + nd⁵ τ + d⁴ (n² + nτ) + d³ (n²τ + n³) + n³d²τ). This bound matches the current record bound Õ_B (d⁶ + d⁵ τ) for the problem of computing the topology of a planar algebraic curve given in implicit form. For planar and space curves, if N = max{d, τ}, the complexity of PTOPO becomes Õ_B (N⁶), which improves the state-of-the-art result, due to Alcázar and Díaz-Toca [CAGD'10], by a factor of N¹⁰. However, visualizing the curve on top of the abstract graph construction, increases the bound to Õ_B (N⁷). We have implemented PTOPO in maple for the case of planar curves. Our experiments illustrate its practical nature.

References

[1]

S. S. Abhyankar and C. J. Bajaj. Automatic parameterization of rational curves and surfaces IV: Algebraic space curves. ACM Trans. Graph., 8(4):325--334, 1989.

Digital Library

[2]

L. Alberti, B. Mourrain, and J. Wintz. Topology and arrangement computation of semi-algebraic planar curves. CAGD, 25(8):631--651, 2008.

Digital Library

[3]

J. G. Alcázar and G. M. Díaz-Toca. Topology of 2D and 3D rational curves. CAGD, 27(7):483--502, 2010.

[4]

S. Basu, R. Pollack, and M-F.Roy. Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, 2003.

[5]

A. Bernardi, A. Gimigliano, and M. Idà. Singularities of plane rational curves via projections. J. Symb. Comput., 09 2016.

[6]

A. Blasco and S. Pérez-Díaz. An in depth analysis, via resultants, of the singularities of a parametric curve. CAGD, 68:22--47, 2019.

[7]

J.-D. Boissonnat and M. Teillaud, editors. Effective Computational Geometry for Curves and Surfaces. Springer-Verlag, Mathematics and Visualization, 2006.

[8]

Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget, F. Rouillier, and M. Sagraloff. Solving bivariate systems using Rational Univariate Representations. J. Complexity, 37:34--75, 2016.

Digital Library

[9]

Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier. Rational univariate representations of bivariate systems and applications. In Proc. 38th Int'l Symp. on Symbolic and Algebraic Computation, ISSAC '13, pages 109--116, NY, USA, 2013. ACM.

Digital Library

[10]

Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier. Separating linear forms and rational univariate representations of bivariate systems. J. Symb. Comput., pages 84--119, 2015.

Digital Library

[11]

L. Busé, C. Laroche, and F. Yıldırım. Implicitizing rational curves by the method of moving quadrics. Computer-Aided Design, 114:101--111, 2019.

[12]

J. Caravantes, M. Fioravanti, L. Gonzalez-Vega, and I. Necula. Computing the topology of an arrangement of implicit and parametric curves given by values. In V. P. Gerdt, W. Koepf, W. M. Seiler, and E. V. Vorozhtsov, editors, Computer Algebra in Scientific Computing, pages 59--73, Cham, 2014. Springer.

[13]

D. Cox, A. Kustin, C. Polini, and B. Ulrich. A study of singularities on rational curves via syzygies. Memoirs of the American Mathematical Society, 222, 02 2011.

[14]

D. N. Diatta, S. Diatta, F. Rouillier, M.-F. Roy, and M. Sagraloff. Bounds for polynomials on algebraic numbers and application to curve topology. arXiv preprint arXiv:1807.10622, 2018.

[15]

D. I. Diochnos, I. Z. Emiris, and E. P. Tsigaridas. On the asymptotic and practical complexity of solving bivariate systems over the reals. J. Symb. Comput., 44(7):818--835, 2009. (Special issue on ISSAC 2007).

Digital Library

[16]

R. T. Farouki, C. Giannelli, and A. Sestini. Geometric design using space curves with rational rotation-minimizing frames. In M. Dæhlen, M. Floater, T. Lyche, J.-L. Merrien, K. Mørken, and L. L. Schumaker, editors, Mathematical Methods for Curves and Surfaces, pages 194--208. Springer, 2010.

Digital Library

[17]

W. Fulton. Algebraic Curves. An Introduction to Algebraic Geometry. Addison Wesley, 1969.

[18]

X.-S. Gao and S.-C. Chou. Implicitization of rational parametric equations. J. Symb. Comput., 14(5):459--470, 1992.

Digital Library

[19]

J. Gutierrez, R. Rubio, and D. Sevilla. On multivariate rational function decomposition. J. Symb. Comput., 33(5):545--562, 2002.

Digital Library

[20]

J. Gutierrez, R. Rubio, and J.-T. Yu. D-resultant for rational functions. Proc. American Mathematical Society, 130, 08 2002.

[21]

X. Jia, X. Shi, and F. Chen. Survey on the theory and applications of μ-bases for rational curves and surfaces. J. Comput. Appl. Math., 329:2--23, 2018.

Digital Library

[22]

A. Kobel and M. Sagraloff. On the complexity of computing with planar algebraic curves. J. Complexity, 31, 08 2014.

[23]

Y.-M. Li and R. J. Cripps. Identification of inflection points and cusps on rational curves. CAGD, 14(5):491--497, 1997.

Digital Library

[24]

T. Lickteig and M.-F. Roy. Sylvester-Habicht sequences and fast Cauchy index computation. J. Symb. Comput., 31(3):315--341, Mar. 2001.

Digital Library

[25]

K. Mahler. On some inequalities for polynomials in several variables. J. London Mathematical Society, 1(1):341--344, 1962.

[26]

D. Manocha and J. F. Canny. Detecting cusps and inflection points in curves. CAGD, 9(1):1--24, 1992.

Digital Library

[27]

V. Pan and E. Tsigaridas. Accelerated approximation of the complex roots and factors of a univariate polynomial. Theor. Computer Science, 681:138--145, 2017.

[28]

H. Park. Effective computation of singularities of parametric affine curves. J. Pure and Applied Algebra, 173:49--58, 08 2002.

[29]

S. Pérez-Díaz. On the problem of proper reparametrization for rational curves and surfaces. CAGD, 23(4):307--323, 2006.

[30]

S. Pérez-Díaz. Computation of the singularities of parametric plane curves. J. Symb. Comput., 42(8):835--857, 2007.

Digital Library

[31]

C. A. T. Recio. Plotting missing points and branches of real parametric curves. Applicable Algebra in Engineering, Communication and Computing, 18, 02 2007.

[32]

R. Rubio, J. Serradilla, and M. Vélez. Detecting real singularities of a space curve from a real rational parametrization. J. Symb. Comput., 44(5):490--498, 2009.

Digital Library

[33]

A. Schönhage. Probabilistic computation of integer polynomial gcds. J. Algorithms, 9(3):365--371, 1988.

Digital Library

[34]

T. W. Sederberg. Improperly parametrized rational curves. CAGD, 3(1):67--75, May 1986.

Digital Library

[35]

T. W. Sederberg and F. Chen. Implicitization using moving curves and surfaces. In Proc. of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '95, pages 301--308, NY, USA, 1995.

Digital Library

[36]

J. R. Sendra. Normal parametrizations of algebraic plane curves. J. Symb. Comput., 33:863--885, 2002.

Digital Library

[37]

J. R. Sendra and F. Winkler. Algorithms for rational real algebraic curves. Fundam. Inf., 39(1,2):211--228, Apr. 1999.

[38]

J. R. Sendra, F. Winkler, and S. Pérez-Díaz. Rational algebraic curves. Algorithms and Computation in Mathematics, 22, 2008.

[39]

A. Strzebonski and E. Tsigaridas. Univariate real root isolation in an extension field and applications. J. Symb. Comput., 92:31--51, 2019.

[40]

J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, 3rd edition, 2013.

[41]

R. J. Walker. Algebraic curves. Springer-Verlag, 1978.

Cited By

Katsamaki CRouillier FTsigaridas EZafeirakopoulos Z(2023) PTOPOJournal of Symbolic Computation10.1016/j.jsc.2022.08.012115:C(427-451)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.08.012
Alcázar JDiaz-Toca G(2023)Computing the topology of the image of a parametric planar curve under a birational transformationComputer Aided Geometric Design10.1016/j.cagd.2023.102189(102189)Online publication date: Mar-2023
https://doi.org/10.1016/j.cagd.2023.102189
Tan LLi BZhang BCheng J(2023)An Algorithm for the Intersection Problem of Planar Parametric CurvesComputer Algebra in Scientific Computing10.1007/978-3-031-41724-5_17(312-329)Online publication date: 24-Aug-2023
https://doi.org/10.1007/978-3-031-41724-5_17
Show More Cited By

Index Terms

On the geometry and the topology of parametric curves
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials

Recommendations

PTOPO: Computing the geometry and the topology of parametric curves
Abstract
We consider the problem of computing the topology and describing the geometry of a parametric curve in R n. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our ...
3D Reconstruction of parametric curves: recovering the control points

This article introduces a new curve reconstruction method based on recovering the control points of parametric cubic curves. The method developed here has two stages: finding the 3D control points of parametric curves and reconstruction of free curves. ...
Parametric curves on meshes
GRAPHITE '05: Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia

In this paper, we propose a method for creating parametric curves on triangular meshes. A curve on a mesh is frequently used as a boundary curve of a specific region of a mesh in mesh modeling and applications such as texture mapping, remeshing or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '20: Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation

July 2020

480 pages

ISBN:9781450371001

DOI:10.1145/3373207

General Chairs:
Ioannis Z. Emiris
National and Kapodistrian University of Athens, ATHENA Research and Innovation Center, Greece
,
Lihong Zhi
Academia Sinica, China
,
Publications Chair:
Angelos Mantzaflaris
Inria, France

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Union?s Horizon 2020
Campus France
Agence Nationale de la Recherche
Fondation Mathématique Jacques Hadamard
Tübitak

Conference

ISSAC '20

ISSAC '20: International Symposium on Symbolic and Algebraic Computation

July 20 - 23, 2020

Kalamata, Greece

Acceptance Rates

ISSAC '20 Paper Acceptance Rate 58 of 102 submissions, 57%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
40
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Katsamaki CRouillier FTsigaridas EZafeirakopoulos Z(2023) PTOPOJournal of Symbolic Computation10.1016/j.jsc.2022.08.012115:C(427-451)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.08.012
Alcázar JDiaz-Toca G(2023)Computing the topology of the image of a parametric planar curve under a birational transformationComputer Aided Geometric Design10.1016/j.cagd.2023.102189(102189)Online publication date: Mar-2023
https://doi.org/10.1016/j.cagd.2023.102189
Tan LLi BZhang BCheng J(2023)An Algorithm for the Intersection Problem of Planar Parametric CurvesComputer Algebra in Scientific Computing10.1007/978-3-031-41724-5_17(312-329)Online publication date: 24-Aug-2023
https://doi.org/10.1007/978-3-031-41724-5_17
Katsamaki CRouillier FTsigaridas EZafeirakopoulos Z(2020)PTOPOACM Communications in Computer Algebra10.1145/3427218.342722354:2(49-52)Online publication date: 29-Sep-2020
https://doi.org/10.1145/3427218.3427223

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents