Numeric certified algorithm for the topology of resultant and discriminant curves

Guillaume Moroz 1 Marc Pouget 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Let $\mathcal C$ be a real plane algebraic curve defined by the resultant of twopolynomials (resp. by the discriminant of a polynomial). Geometrically such acurve is the projection of the intersection of the surfaces$P(x,y,z)=Q(x,y,z)=0$ (resp. $P(x,y,z)=\frac{\partial P}{\partial z}(x,y,z)=0$),and generically its singularities are nodes (resp. nodes and ordinary cusp).State-of-the-art numerical algorithms cannot handle the computation of itstopology. The main challenge is to find numerical criteria that guarantee theexistence and the uniqueness of a singularity inside a given box $B$, whileensuring that $B$ does not contain any closed loop of $\mathcal{C}$. We solvethis problem by providing a square deflation system that can be used to certifynumerically whether $B$ contains a singularity $p$. Then we introduce a numericadaptive separation criterion based on interval arithmetic to ensure that thetopology of $\mathcal C$ in $B$ is homeomorphic to the local topology at $p$.
Complete list of metadatas

https://hal.inria.fr/hal-01093040
Contributor : Marc Pouget <>
Submitted on : Wednesday, January 7, 2015 - 3:31:44 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:26 PM
Long-term archiving on : Saturday, September 12, 2015 - 12:35:37 AM

File

RR-8653.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01093040, version 2
  • ARXIV : 1412.3290

Citation

Guillaume Moroz, Marc Pouget. Numeric certified algorithm for the topology of resultant and discriminant curves. [Research Report] RR-8653, Inria. 2014. ⟨hal-01093040v2⟩

Share

Metrics

Record views

32

Files downloads

79