4 papers · 1 filter
Quadratic Reconfiguration of Plane Spanning Paths on Two-Layer Point Sets
Samuel Avril, Yan Gerard, Guilherme D. da Fonseca
Consider a crossing-free polygonal path with vertices and a flip operation that removes an edge and adds another one, without changing the vertex set and keeping the path cross…
Shadoks Approach to Parallel Reconfiguration of Triangulations
Guilherme D. da Fonseca, Fabien Feschet, Yan Gerard
We describe the methods used by Team Shadoks to win the CG:SHOP 2026 Challenge on parallel reconfiguration of planar triangulations. An instance is a collection of triangulations o…
Untangling Segments in the Plane
Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier
A set of n segments in the plane may form a Euclidean TSP tour, a tree, or a matching, among others. Optimal TSP tours as well as minimum spanning trees and perfect matchings have…
Shadoks Approach to Knapsack Polygonal Packing
Guilherme D. da Fonseca, Yan Gerard
The 2024 edition of the CG:SHOP Challenge focused on the knapsack polygonal packing problem. Each instance consists of a convex polygon known as the container and a multiset of ite…