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…

Untangling Segments

In the Euclidean Travelling Salesman Problem (TSP), we are given a set P of n points in the plane and the goal is to produce a closed tour connecting all points of minimum total Euclidean length. The TSP problem, both in the Euclidean and in the more general graph versions, is one of the most…

CG:SHOP 2022 – Coloring Segments

The fourth edition of the competition CG:SHOP 2022 has announced the final results of the challenge. Being part of the Shadoks with Guilherme Da Fonseca, Loïc Crombez and Aldo Gonzalez-Lorenzo, we obtained good results with 225 best solutions on the 225 instances and thus the first place of the challenge. The problem consists in coloring…

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…

[Open problem] About the Reconstruction of Convex Lattice Sets in Discrete Tomography: New Results

We consider the following problem: Input: two vectors of integers H in R^Z^m and V in Z^n. Output: a convex lattice set having H and V as horizontal and vertical X-rays (look at Fig.1 for a better understanding, the problem is really simple) Fig. 1 – The problem that we consider takes two vectors as…

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…