Papers & slides

___________________________________________________________________________________________________ SHOP2019 – paper submitted to ACM Journal of Experimental Algorithmics Loïc Crombez, Guilherme da Fonseca, Yan Gerard: Greedy and Local Search Heuristics to Build Area-Optimal Polygons Paper: CGSHOP19journal No ArXiv or Hall version right now… The code of the algorithm written in Python -poLYG – is available on GitHub . It is less than…

CG:SHOP 2021 – Coordinated Motion Planning

This year, the challenge of Computational Geometry CG:SHOP 2021 deals with a problem of coordinated motion planning. In other words, the problem is to move robots in a grid in order to send them from an initial position -each robot is in a square cell- to a target position. At each time, it is forbidden…

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…

CG: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,…

CG: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 SHOP2019.  They submitted to the community a challenge of Optimal Area Polygonalization by providing some data (other challenges have followed in 2020 and 2021)….

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…