3 citations · 9 across the 9 of their papers we have counts for
13 papers
Bounded-Support Additive Latin Transversals
Antoine Deza, Yan Gerard, Yijun Ma +1
We consider the following additive Latin transversal problem. Given a multiset of elements of and a set of cardinality …
Lozenge Tiling by Computing Distances
Jean-Marie Favreau, Yan Gerard, Pascal Lafourcade +1
The Calisson puzzle is a tiling puzzle in which one must tile a triangular grid inside a hexagon with lozenges, under the constraint that certain prescribed edges remain tile bound…
Short Flip Sequences to Untangle Segments in the Plane
Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier
A (multi)set of segments in the plane may form a TSP tour, a matching, a tree, or any multigraph. If two segments cross, then we can reduce the total length with the following flip…
The Calissons Puzzle
Jean-Marie Favreau, Yan Gerard, Pascal Lafourcade +1
In 2022, Olivier Longuet, a French mathematics teacher, created a game called the \textit{calissons puzzle}. Given a triangular grid in a hexagon and some given edges of the grid,…
Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring
Loïc Crombez, Guilherme D. da Fonseca, Florian Fontan +8
CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the to…
Reconstruction of Convex Sets from One or Two X-rays
Yan Gerard
We consider a class of problems of Discrete Tomography which has been deeply investigated in the past: the reconstruction of convex lattice sets from their horizontal and/or vertic…
On the Longest Flip Sequence to Untangle Segments in the Plane
Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier
A set of segments in the plane may form a Euclidean TSP tour or a matching, among others. Optimal TSP tours as well as minimum weight perfect matchings have no crossing segments, b…
Complexity Results on Untangling Red-Blue Matchings
Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca +2
Given a matching between n red points and n blue points by line segments in the plane, we consider the problem of obtaining a crossing-free matching through flip operations that re…
Greedy and Local Search Heuristics to Build Area-Optimal Polygons
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard
In this paper, we present our heuristic solutions to the problems of finding the maximum and minimum area polygons with a given set of vertices. Our solutions are based mostly on t…
Shadoks Approach to Low-Makespan Coordinated Motion Planning
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard +3
This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge. This year's problem is to coordinate the motion of multiple robots in order to reach th…
Efficient Algorithms for Battleship
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard
We consider an algorithmic problem inspired by the Battleship game. In the variant of the problem that we investigate, there is a unique ship of shape which has bee…
Efficient Algorithms to Test Digital Convexity
Loïc Crombez, Guilherme D. da Fonseca, Yan Gérard
A set is digital convex if , where denotes the convex hull of . In this paper, we consider the algorithmic prob…
Peeling Digital Potatoes
Loïc Crombez, Guilherme D. da Fonseca, Yan Gérard
The potato-peeling problem (also known as convex skull) is a fundamental computational geometry problem and the fastest algorithm to date runs in time for a polygon with $…