Papers & slides

___________________________________________________________________________________________________ Conference DGCI 2019 Loïc Crombez, Guilherme da Fonseca, yan gérard: Efficient Algorithms to test Digital Convexity. Paper: DGCI2019 – Efficient algorithms for testing digital convexity @inproceedings{DBLP:conf/dgci/CrombezFG19, author = {Lo{\”{\i}}c Crombez and Guilherme Dias da Fonseca and Yan G{\'{e}}rard}, title = {Efficient Algorithms to Test Digital Convexity}, booktitle = {Discrete Geometry for Computer Imagery -…

Optimal area polygonalization

The ideas and images presented there are mostly due to Guilherme Da Fonseca and Loïc Crombez, our PhD student. For the 2019 edition of SoCG 2019, the main conference of Computational Geometry, Joseph Mitchell , Erik Demaine and Sándor Fekete have organized a very interesting workshop  CG:Solving Hard Optimization Problems. They submitted to the community…

Testing digital convexity

With Loïc Crombez (PhD student) and Guilherme Da Fonseca, we have been interested in the question of testing whether a given subset of the lattice Z^d is convex (in other words, if it is equal to the intersection of its real convex hull with the integer lattice set). We provided a linear time algorithm in…

Convex aggregation problems in Z²

No, the front image not an advertising for drinking wine or eating grapes! but for an original family of combinatorial problems that I called “convex aggregation problems”. They are problems of Digital Computational Geometry… These problems come from Discrete Tomography but they can be considered without having any idea of their origin. In (unary) convex…

Discrete rotation patterns…

The following images are obtained with discrete rotations. Let us consider the lattice Z². By applying a rotation of given angle a, most of the lattice points have images with non integral coordinates. Then a discrete rotation is the combination of a real rotation followed by a rounding step (for instance round(x,y)=(floor(x+1/2),floor(y+1/2)) ). Let us…

Discrete Tomography – A survey about some combinatorial results

I don’t know if it is possible to cook an omelette without breaking eggs (that’s a french expression: we don’t cook omelettes without breaking eggs) but I know that it’s possible to see inside it… It is possible to determine the slices with the white and yellow matter without breaking the shell. With computerized tomography….

Peeling digital potatoes

The “Peeling potatoes problem” also called “digital skull” problem is to find the largest convex subset of a given polygon. In the digital framework, the polygon is replaced by a finite lattice set and the solution is the largest digitally convex lattice set that it contains (a presentation of the digital version of the problem…

TFJM 2017: the tree which hides the forest

The TFJM is a french tournament for the young mathematicians in french highschools (or at least speaking french). Thanks to Pierre-Antoine Guihéneuf, the second problem of the 2017 edition – TFJM2017 – l’arbre qui cache la forêt turns around the notion of lattice jewel that I introduced in the framework of polyhedral separation in the…

Derivatives of a digital function with finite differences

The finite differences allow to compute some approximations of the derivatives of a function f by using some linear combinations of the values of f at equidistant abscissa (the step between two consecutive values of f is denoted h).  If the values of f have been rounded, the error on each value of f introduces…