SIVIGNON

Isabelle

Chargée de Recherche CNRS

Research

*Note:* If no licence is specified, all these codes are freely available
but without any warranty.

- Digital surface decomposition (DSD) into digital plane segments: also includes a simple graphical interface for 3D digital objects display;
- Reduction of a 3-SAT boolean formula into a digital object surface (SatDSD): used to prove that the minimal decomposition of a digital surface into digital plane segments is NP-hard.

- Digital curve simplification using the Fréchet distance: a fast and guaranteed algorithm. We propose both a software and an ipelet (to be used with IPE) that computes a greedy simplification of a digital curve according to the Fréchet distance, following the algorithm presented in the paper of DGCI 2011.

- Digital Straight Line Subsegment: an algorithm to recognize a DSS in logarithmic time when a DSL container in known. The code uses the open-source library DGtal and is a feature of the library. It implements the algorithms of the paper "Fast recognition of a Digital Straight Line Subsegment: two algorithms of logarithmic time complexity", Discrete Applied Mathematics 183: 130-146 (2015). A preliminary version of one of the algorithms has been presented during the DGCI 2013 conference ("Walking in the Farey fan to Compute the Characteristics of a Discrete Straight Line Subsegment", Isabelle Sivignon, LNCS 7749).

- Implementation of the algorithm presented in "Algorithms for Fast Digital Straight Segments Union". Isabelle Sivignon, International Conference on Discrete Geometry for Computer Imagery 2014, Springer LNCS 344-357. It computes the minimal characteristics of the digital straight line containing two given digital straight segments. The code is part of the DGtal library, as a method of the class ArithmeticalDSS.

- Implementation of the algorithm presented in "A note on the computation of the fraction of smallest denominator in between two irreducible fractions". Isabelle Sivignon, Discrete Applied Mathematics 202: 197-201 (2016). Given two irreducible fractions, it computes the fraction of smallest denominator in between. The algorithm is output-sensitive, with a linear complexity with respect to the depth of the result fraction. Python code is available here, and a c++ implementation is available in the DGtal library, as a method of the Stern Brocot class.

- In "(δ,ε)-ball approximation of a shape: definition and complexity", we prove that the problem is NP-complete. The proof is made through a reduction from a variant of the vertex cover problem, with a well-defined geometric construction for any cubic planar graph. In appendix of the article, we provide a specific vertex gadget for degree-three vertices when δ=0 and claim that this gadget actually remains valid for any value of δ. We provide here a Geogebra file that gives a parameterized generic construction of this gadget for any values of δ and ε.

- In "Efficient Distance Transformation for Path-based Metrics", we provide efficient separable algorithms to compute distance transformation for shapes in nD images and path-based metrics. In particular, we provide an algorithm for which the complexity depends on the geometry of the cut of a rational ball (ball that defines the metric) by a 2-flat. Python code used to generate rational balls from nD Farey Sequences and to study the number of vertices of the cut is available here: it uses Qhull to compute convex hulls and cuts by hyperplanes.

Other material concerning digital geometry is available on the IAPR-TC18 webpage.

Grenoble Images Parole Signal Automatique laboratoire

UMR 5216 CNRS - Grenoble INP - Université Joseph Fourier - Université Stendhal