We describe the methods used by Team Shadoks to win the CG:SHOP 2026 Challenge on parallel reconfiguration of planar triangulations. Our approach combines exact methods based on SAT with several greedy heuristics, and also makes use of SAT and MaxSAT for solution improvement.

Description of the solvers used by the Shadoks team in the PACE 2025 challenge. The challenge considers solvers for the minimum dominating set and hitting set problems. For the heuristic challenge, we respectively won third and fourth place for hitting set and dominating set. For the exact challenge, we won fifth place on both problems.

Deep Brain Stimulation (DBS) has proven its efficiency in the treatment of Parkinson’s disease or essential tremor. It requires precise localizations of targets for instance in the thalamus. Since deep brain structures have been shown to be hardly visible on T1 or T2 weighted imaging, most methods rely on atlas based comparison and registration. It is however possible to use direct targeting using a specific MRI sequence called WAIR (White Matter Attenuated Inversion Recovery) even on 1.5 Tesla MRI machine. The direct targeting facilitates the precise segmentation of deep brain structures needed to plan the trajectories of the electrodes for the DBS. But this remains a tedious delineation necessarily done by a neurosurgeon to avoid misinterpretation of the images. In this paper, we propose to build an isotropic super-resolution image for WAIR imaging to facilitate precise direct targeting of anatomical structures in the deep brain. We present a method to perform the reconstruction of a high resolution isotropic WAIR volume from three acquisitions performed on a volunteer subject. The method is based on transfinite interpolation in convex cells of an hyperplane arrangement. Our results show promising quality reconstruction for the computation of a super-resolution WAIR. It allows unambiguous segmentation of the deep brain to be used in DBS surgery.

The issue of decomposing digital shapes into sets of digital primitives has been widely studied over the years. Practically all existing approaches require perfect or cleaned shapes. Those are obtained using various pre-processing techniques such as thinning or skeletonization. The aim of this paper is to bypass the use of such pre-processings, in order to obtain decompositions of shapes directly from connected components. This method has the advantage of taking into account the intrinsic thickness of digital shapes, and provides a decomposition which is also robust to noise.

This paper deals with the construction of a non parametric multiscale analysis from a 1D parametric decomposition of shapes where the elements of the decomposition are geometric primitives. We focus on the case of linear structures in shapes but our construction readily extends to the case of any geometric primitives. One key point of the construction is that it is truly multiscale in the sense that a higher level is a sublevel of a lower one and that it preserves symmetries of shapes. We made some experiments to show the simplification it provides on classical shapes. Results are promising.

A theory for the multiscale analysis of digital shapes would be very interesting for the pattern recognition community, giving a digital equivalent of the continuous scale-space theory. We focus here on providing analytical formulae of the multiresolution of Digital Straight Segments (DSS), which is a fundamental tool for describing digital shape contours.

Digital straightness is a fundamental geometric characteristic in computer science. There have been a lot of equivalent definitions in the past. In the present study, we base our work on the notion of lattice width which is related to the notion of direction of a digital set. Our approach not only applies to thin digital curves but also to thick digital sets. We identify a criterion to detect digital curves that can be considered as nearly straight and we call them quasi-straight digital segments. Experiments are provided on raw data sets with no preprocessing. The results are promising.

Cellular automata are a massively parallel computation model with discrete time and local rules. They are well adapted to biological or physical simulations. However, they are intrinsically anisotropic. The possibility of computing isotropic figures on cellular automata such as circles has already been proved.4 Moreover, the previous construction enables to compute all the major discretizations known in the literature. We present in this article an extension of this work to the construction of spheres in three dimensions. A local characterization of a sphere is presented based upon the relationship between spheres and circles. This leads to the possibility of constructing a family of concentric discrete spheres in real time. Moreover, the approach can use many discretization schemes leading to the construction of various discrete spheres as done for circles.