Computational Geometry

Our work in computational geometry focuses on algebraic tools for certified drawings (and topology) of real curves and surfaces.

Most of the developments are done in collaboration with the GAMBLE  Project Team.ridges

Related publications

  • [PDF] [DOI] S. Lazard, M. Pouget, and F. Rouillier, “Bivariate triangular decompositions in the presence of asymptotes,” Journal of Symbolic Computation, vol. 82, pp. 123-133, 2017.
    [Bibtex] 
    @article{lazard:hal-01468796,
TITLE = {{Bivariate triangular decompositions in the presence of asymptotes}},
AUTHOR = {Lazard, Sylvain and Pouget, Marc and Rouillier, Fabrice},
URL = {https://hal.inria.fr/hal-01468796},
JOURNAL = {{Journal of Symbolic Computation}},
PUBLISHER = {{Elsevier}},
VOLUME = {82},
PAGES = {123 - 133},
YEAR = {2017},
DOI = {10.1016/j.jsc.2017.01.004},
PDF = {https://hal.inria.fr/hal-01468796/file/JSC.pdf},
HAL_ID = {hal-01468796},
HAL_VERSION = {v1},
}
  • [PDF] [DOI] Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget, F. Rouillier, and M. Sagraloff, “Solving bivariate systems using Rational Univariate Representations,” Journal of Complexity, vol. 37, p. 34–75, 2016.
    [Bibtex] 
    @article{bouzidi:hal-01342211,
TITLE = {{Solving bivariate systems using Rational Univariate Representations}},
AUTHOR = {Bouzidi, Yacine and Lazard, Sylvain and Moroz, Guillaume and Pouget, Marc and Rouillier, Fabrice and Sagraloff, Michael},
URL = {https://hal.inria.fr/hal-01342211},
JOURNAL = {{Journal of Complexity}},
PUBLISHER = {{Elsevier}},
VOLUME = {37},
PAGES = {34--75},
YEAR = {2016},
DOI = {10.1016/j.jco.2016.07.002},
PDF = {https://hal.inria.fr/hal-01342211/file/JoC.pdf},
HAL_ID = {hal-01342211},
HAL_VERSION = {v2},
}
  • [DOI] A. Kobel, F. Rouillier, and M. Sagraloff, “Computing Real Roots of Real Polynomials … and now For Real!,” in ISSAC ’16 Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada, 2016, p. 7.
    [Bibtex] 
    @inproceedings{kobel:hal-01363955,
TITLE = {{Computing Real Roots of Real Polynomials ... and now For Real!}},
AUTHOR = {Kobel, Alexander and Rouillier, Fabrice and Sagraloff, Michael},
URL = {https://hal.inria.fr/hal-01363955},
BOOKTITLE = {{ ISSAC '16 Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation}},
ADDRESS = {Waterloo, Canada},
SERIES = { ISSAC '16 Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation},
PAGES = {7},
YEAR = {2016},
MONTH = Jul,
DOI = {10.1145/2930889.2930937},
KEYWORDS = {real roots ; univariate polynomials ; root finding ; root iso- lation ; Newton's method ; Descartes method ; approximate arithmetic ; certified computation},
HAL_ID = {hal-01363955},
HAL_VERSION = {v1},
}
  • [PDF] [DOI] Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget, F. Rouillier, and M. Sagraloff, “Solving bivariate systems using Rational Univariate Representations,” Journal of Complexity, vol. 37, p. 34–75, 2016.
    [Bibtex] 
    @article{bouzidi:hal-01342211,
TITLE = {{Solving bivariate systems using Rational Univariate Representations}},
AUTHOR = {Bouzidi, Yacine and Lazard, Sylvain and Moroz, Guillaume and Pouget, Marc and Rouillier, Fabrice and Sagraloff, Michael},
URL = {https://hal.inria.fr/hal-01342211},
JOURNAL = {{Journal of Complexity}},
PUBLISHER = {{Elsevier}},
VOLUME = {37},
PAGES = {34--75},
YEAR = {2016},
DOI = {10.1016/j.jco.2016.07.002},
PDF = {https://hal.inria.fr/hal-01342211/file/JoC.pdf},
HAL_ID = {hal-01342211},
HAL_VERSION = {v2},
}
  • [DOI] A. Kobel, F. Rouillier, and M. Sagraloff, “Computing Real Roots of Real Polynomials … and now For Real!,” in ISSAC ’16 Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada, 2016, p. 7.
    [Bibtex] 
    @inproceedings{kobel:hal-01363955,
TITLE = {{Computing Real Roots of Real Polynomials ... and now For Real!}},
AUTHOR = {Kobel, Alexander and Rouillier, Fabrice and Sagraloff, Michael},
URL = {https://hal.inria.fr/hal-01363955},
BOOKTITLE = {{ ISSAC '16 Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation}},
ADDRESS = {Waterloo, Canada},
SERIES = { ISSAC '16 Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation},
PAGES = {7},
YEAR = {2016},
MONTH = Jul,
DOI = {10.1145/2930889.2930937},
KEYWORDS = {real roots ; univariate polynomials ; root finding ; root iso- lation ; Newton's method ; Descartes method ; approximate arithmetic ; certified computation},
HAL_ID = {hal-01363955},
HAL_VERSION = {v1},
}
  • Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier, “Separating linear forms and rational univariate representations of bivariate systems,” Journal of Symbolic Computation, pp. 84-119, 2015.
    [Bibtex] 
    @article{BLPR15,
Author = {Bouzidi, Yacine and Lazard, Sylvain and Pouget, Marc and Rouillier, Fabrice},
Hal_Id = {hal-00977671},
Hal_Version = {v1},
Journal = {{Journal of Symbolic Computation}},
Keywords = {Bivariate system ; Separating Linear Form ; Rational univariate representation},
Pages = {84-119},
Publisher = {{Elsevier}},
Title = {Separating linear forms and Rational Univariate Representations of bivariate systems},
Url = {https://hal.inria.fr/hal-00977671},
Year = {2015},
Bdsk-Url-1 = {https://hal.inria.fr/hal-00977671}}
  • Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget, and F. Rouillier, “Improved algorithm for computing separating linear forms for bivariate systems,” in ISSAC – 39th International Symposium on Symbolic and Algebraic Computation, Kobe, Japan, 2014.
    [Bibtex] 
    @inproceedings{BLPR14,
Address = {Kobe, Japan},
Author = {Bouzidi, Yacine and Lazard, Sylvain and Moroz, Guillaume and Pouget, Marc and Rouillier, Fabrice},
Booktitle = {{ISSAC - 39th International Symposium on Symbolic and Algebraic Computation}},
Hal_Id = {hal-00992634},
Hal_Version = {v1},
Month = Jul,
Title = {Improved algorithm for computing separating linear forms for bivariate systems},
Url = {https://hal.inria.fr/hal-00992634},
Year = {2014},
Bdsk-Url-1 = {https://hal.inria.fr/hal-00992634}}
  • [DOI] D. N. Diatta, F. Rouillier, and M. Roy, “On the computation of the topology of plane curves,” in Proceedings of the 39th international symposium on symbolic and algebraic computation, New York, NY, USA, 2014, p. 130–137.
    [Bibtex] 
    @inproceedings{DRR14,
Acmid = {2608670},
Address = {New York, NY, USA},
Author = {Diatta, Daouda Niang and Rouillier, Fabrice and Roy, Marie-Fran\c{c}oise},
Booktitle = {Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation},
Doi = {10.1145/2608628.2608670},
Isbn = {978-1-4503-2501-1},
Keywords = {algebraic curves, exact topology computation},
Location = {Kobe, Japan},
Numpages = {8},
Pages = {130--137},
Publisher = {ACM},
Series = {ISSAC '14},
Title = {On the Computation of the Topology of Plane Curves},
Url = {http://doi.acm.org/10.1145/2608628.2608670},
Year = {2014},
Bdsk-Url-1 = {http://doi.acm.org/10.1145/2608628.2608670},
Bdsk-Url-2 = {http://dx.doi.org/10.1145/2608628.2608670}}
  • Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier, “Separating linear forms for bivariate systems,” in ISSAC – 38th International Symposium on Symbolic and Algebraic Computation, Boston, United States, 2013, pp. 117-124.
    [Bibtex] 
    @inproceedings{BLPR13a,
Address = {Boston, United States},
Author = {Bouzidi, Yacine and Lazard, Sylvain and Pouget, Marc and Rouillier, Fabrice},
Booktitle = {{ISSAC - 38th International Symposium on Symbolic and Algebraic Computation}},
Hal_Id = {hal-00809425},
Hal_Version = {v1},
Keywords = {Bivariate system ; Separating Linear Form},
Month = Jun,
Pages = {117-124},
Title = {Separating Linear Forms for Bivariate Systems},
Url = {https://hal.inria.fr/hal-00809425},
Year = {2013},
Bdsk-Url-1 = {https://hal.inria.fr/hal-00809425}}
  • Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier, “Rational univariate representations of bivariate systems and applications,” in ISSAC – 38th International Symposium on Symbolic and Algebraic Computation, Boston, United States, 2013, pp. 109-116.
    [Bibtex] 
    @inproceedings{BLPR13b,
Address = {Boston, United States},
Author = {Bouzidi, Yacine and Lazard, Sylvain and Pouget, Marc and Rouillier, Fabrice},
Booktitle = {{ISSAC - 38th International Symposium on Symbolic and Algebraic Computation}},
Hal_Id = {hal-00809430},
Hal_Version = {v1},
Keywords = {Bivariate system ; Rational univariate representation},
Month = Jun,
Pages = {109-116},
Title = {Rational Univariate Representations of Bivariate Systems and Applications},
Url = {https://hal.inria.fr/hal-00809430},
Year = {2013},
Bdsk-Url-1 = {https://hal.inria.fr/hal-00809430}}
  • Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier, “New bivariate system solver and topology of algebraic curves,” in Eurocg 2011, 2011.
    [Bibtex] 
    @Conference{BLPR11,
Title = {New bivariate system solver and topology of algebraic curves},
Author = {Bouzidi, Y. and Lazard, S. and Pouget, M. and Rouillier, F.},
Booktitle = {EuroCG 2011},
Year = {2011},
Owner = {rouillie},
Timestamp = {2011.03.01}
}
  • [DOI] F. Rouillier, “On solving systems of bivariate polynomials.,” in Icms 2010 – mathematical software, 2010, pp. 100-104.
    [Bibtex] 
    @Conference{Rouillier2010,
Title = {On Solving Systems of Bivariate Polynomials.},
Author = {Rouillier, F.},
Booktitle = {ICMS 2010 - MATHEMATICAL SOFTWARE},
Year = {2010},
Pages = {100-104},
Publisher = {Springer},
Series = {Lecture Notes in Computer Science},
Volume = {6327},
Doi = {DOI: 10.1007/978-3-642-15582-6_21},
Owner = {rouillie},
Timestamp = {2010.10.16}
}
  • [DOI] M. Pouget, S. Lazard, E. Tsigaridas, F. Rouillier, L. Peñaranda, and J. Cheng, “On the topology of planar algebraic curves,” in Scg ’09 proceedings of the 25th annual symposium on computational geometry, 2009, pp. 361-370.
    [Bibtex] 
    @Conference{Pouget2009,
Title = {On the topology of planar algebraic curves},
Author = {Pouget, M. and Lazard, S. and Tsigaridas, E. and Rouillier, F. and Pe{\~n}aranda, L. and Cheng, J.},
Booktitle = {SCG '09 Proceedings of the 25th annual symposium on Computational geometry},
Year = {2009},
Pages = {361-370},
Publisher = {ACM New York, NY, USA ©2009},
Date-added = {2009-03-27 13:31:35 +0100},
Date-modified = {2009-03-27 13:34:40 +0100},
Doi = {http://dx.doi.org/10.1145/1542362.1542424},
Owner = {rouillie},
Timestamp = {2010.10.16},
X-editorial-board = {yes},
X-international-audience = {yes},
X-proceedings = {yes}
}
  • F. Cazals, J. -C. Faugère, M. Pouget, and F. Rouillier, “Topologically certified approximation of umbilics and ridges on polynomial parametric surfaces,” in Computational methods for algebraic spline surfaces, 2006.
    [Bibtex] 
    @InProceedings{Cazals2006a,
Title = {Topologically certified approximation of umbilics and ridges on polynomial parametric surfaces},
Author = {F. Cazals and J.-C. Faug\`ere and M. Pouget and F. Rouillier},
Booktitle = {Computational Methods for Algebraic Spline Surfaces},
Year = {2006},
Note = {toappear},
Owner = {rouillie},
Timestamp = {2010.10.16}
}
  • F. Cazals, J. -C. Faugère, M. Pouget, and F. Rouillier, “The implicit structure of ridges of a smooth parametric surface,” Computer aided geometric design, vol. 23, iss. 7, pp. 582-598, 2006.
    [Bibtex] 
    @Article{Cazals2006b,
Title = {The implicit structure of ridges of a smooth parametric surface},
Author = {F. Cazals and J.-C. Faug\`ere and M. Pouget and F. Rouillier},
Journal = {Computer Aided Geometric Design},
Year = {2006},
Note = {INRIA Tech Report 5608},
Number = {7},
Pages = {582-598},
Volume = {23},
Owner = {rouillie},
Timestamp = {2010.10.16},
Url = {https://hal.inria.fr/inria-00081751}
}
  • F.~Rouillier and P.~Zimmermann, “Efficient isolation of polynomial real roots,” Journal of computational and applied mathematics, vol. 162, iss. 1, p. 33–50, 2003.
    [Bibtex] 
    @Article{Rouillier2003,
Title = {Efficient Isolation of Polynomial Real Roots },
Author = {F.~Rouillier and P.~Zimmermann},
Journal = {Journal of Computational and Applied Mathematics},
Year = {2003},
Number = {1},
Pages = {33--50},
Volume = {162},
Owner = {rouillie},
Timestamp = {2010.10.16}
}
  • F.~Rouillier, “Solving zero-dimensional systems through the rational univariate representation,” Journal of applicable algebra in engineering, communication and computing, vol. 9, iss. 5, p. 433–461, 1999.
    [Bibtex] 
    @Article{Rouillier1999a,
Title = {Solving zero-dimensional systems through the rational univariate representation},
Author = {F.~Rouillier},
Journal = {Journal of Applicable Algebra in Engineering, Communication and Computing},
Year = {1999},
Number = {5},
Pages = {433--461},
Volume = {9},
Owner = {rouillie},
Timestamp = {2010.10.16}
}

Comments are closed.