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 -…

The Battleship Complexity of a Shape

We consider the following algorithmic problem: You are playing to the children’s game called battleship, but we change a little bit the rules in order to consider a simpler problem: – There is only one ship, formed by n squares. – The shape of the ship is given and the players are not allowed to…

SHOP:2020 – Minimum Convex Partition

This year, Erik Demaine (MIT), Sándor Fekete (TU Braunschweig), Phillip Keldenich (TU Braunschweig), Dominik Krupke (TU Braunschweig), Joseph S. B. Mitchell (Stony Brook University) have organized a new session of their challenge of Computational Geometry: CG:SHOP2020 in the framework of SoCG2020. 25 teams have participated and with my colleagues, Aldo Lorenzo Gonzales, Guilherme Da Fonseca,…

SHOP:2019 – Optimal Area Polygonalization

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 a challenge of Optimal Area Polygonalization by providing some data. The problem is close to the well-known Travelling salesman…

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 – Survey (about 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 and 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…