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.

Abstract Approximating convex bodies is a fundamental problem in geometry. Given a convex body K in $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> for a fixed dimension d , the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> . The best known uniform bound, due to Dudley (1974), shows that $$O(({{\,\textrm{diam}\,}}(K)/\varepsilon )^{(d-1)/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>diam</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>/</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> facets suffice. Although this bound is optimal for fat objects, such as Euclidean balls, it is far from optimal for “skinny” convex bodies. Skinniness can be characterized relative to the Euclidean ball. Given a convex body K , define its area radius , $${{\,\textrm{arad}\,}}(K)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mtext>arad</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , to be the radius of the Euclidean ball having the same surface area as K . It follows from generalizations of the isoperimetric inequality that $${{\,\textrm{diam}\,}}(K) \ge 2 \cdot {{\,\textrm{arad}\,}}(K)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mtext>diam</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> <mml:mo>·</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>arad</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We show that, given a convex body whose minimum width is at least $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> , it is possible to approximate the body by a polytope having $$O(({{\,\textrm{arad}\,}}(K)/\varepsilon )^{(d-1)/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>arad</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>/</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> facets. Our approach works by first reducing the problem of approximating convex bodies to that of approximating convex functions. We employ a classical concept from convexity, called Macbeath regions. We demonstrate that there is a polar relationship between the Macbeath regions of a function and the Macbeath regions of its Legendre dual. This is combined with known bounds on the Mahler volume to bound the total size of the approximation.

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.

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 items, where each item is a simple polygon with an associated integer value. A feasible packing solution places a selection of the items inside the container without overlapping and using only translations. The goal is to achieve a packing that maximizes the total value of the items in the solution. Our approach to win first place is divided into two main steps. First, we generate promising initial solutions using two strategies: one based on integer linear programming and the other on employing a combination of geometric greedy heuristics. In the second step, we enhance these solutions through local search techniques, which involve repositioning items and exploring potential replacements to improve the total value of the packing.

Abstract. Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body [Formula: see text] and [Formula: see text], a covering is a collection of convex bodies whose union covers [Formula: see text] such that a constant factor expansion of each body lies within an [Formula: see text] expansion of [Formula: see text]. Coverings have been employed in many applications, such as approximations for diameter, width, and [Formula: see text]-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the closest vector problem (CVP). It is known how to construct coverings of size [Formula: see text] for general convex bodies in [Formula: see text]. In special cases, such as when the convex body is the [Formula: see text] unit ball, this bound has been improved to [Formula: see text]. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach–Mazur metric. Given a well-centered convex body [Formula: see text] and an approximation parameter [Formula: see text], we show that there exists a polytope [Formula: see text] consisting of [Formula: see text] vertices (facets) such that [Formula: see text]. This bound is optimal in the worst case up to factors of [Formula: see text]. (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest [Formula: see text]-approximate CVP algorithm that works in any norm, with a running time of [Formula: see text] up to polynomial factors in the input size, and we obtain the fastest [Formula: see text]-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of [Formula: see text]).

International audience

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ε > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an ε expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ε-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the Closest Vector Problem (CVP).

International audience

This article considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body K of unit diameter in Euclidean d -dimensional space (where d is a constant) and an error parameter ε > 0, the objective is to determine a convex polytope of low combinatorial complexity whose Hausdorff distance from K is at most ε. By combinatorial complexity , we mean the total number of faces of all dimensions. Classical constructions by Dudley and Bronshteyn/Ivanov show that O (1/ε ( d -1)/2 ) facets or vertices are possible, respectively, but neither achieves both bounds simultaneously. In this article, we show that it is possible to construct a polytope with O (1/ε ( d -1)/2 ) combinatorial complexity, which is optimal in the worst case. Our result is based on a new relationship between ε-width caps of a convex body and its polar body. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are “essentially different.” We achieve our main result by combining this with a variant of the witness-collector method and a novel variable-thickness layered construction of the economical cap covering.

This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.

Convex bodies play a fundamental role in geometric computation, and approximating such bodies is often a key ingredient in the design of efficient algorithms. We consider the question of how to succinctly approximate a multidimensional convex body by a polytope. We are given a convex body K of unit diameter in Euclidean d-dimensional space (where d is a constant) along with an error parameter ε > 0. The objective is to determine a polytope of low combinatorial complexity whose Hausdorff distance from K is at most e. By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. In the mid-1970's, a result by Dudley showed that O(1/ε(d–1)/2) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices. While both results match known worst-case lower bounds, obtaining a similar upper bound on the total combinatorial complexity has been open for over 40 years. Recently, we made a first step forward towards this objective, obtaining a suboptimal bound. In this paper, we settle this problem with an asymptotically optimal bound of O(1/ε(d–1)/2). Our result is based on a new relationship between ε-width caps of a convex body and its polar. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are “essentially different.” We achieve our result by combining this with a variant of the witness-collector method and a novel variable-width layered construction.

We present a new approach to ε-approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean distances. We consider two families of distance functions: (a) convex scaling distance functions including the Mahalanobis distance, the Minkowski metric and multiplicative weights, and (b) Bregman divergences including the Kullback-Leibler divergence and the Itakura-Saito distance. As the fastest known data structures rely on the lifting transformation, their application is limited to the Euclidean metric, and alternative approaches for other distance functions are much less efficient. We circumvent the reliance on the lifting transformation by a careful application of convexification, which appears to be relatively new to computational geometry. We are given n points in ℝd, each a site possibly defining its own distance function. Under mild assumptions on the growth rates of these functions, the proposed data structures answer queries in logarithmic time using O(n log(1/ε)/εd/2) space, which nearly matches the best known results for the Euclidean metric.

In the polytope membership problem, a convex polytope $K$ in $\mathbb{R}^d$ is given, and the objective is to preprocess $K$ into a data structure so that, given any query point $q \in \mathbb{R}^d$, it is possible to determine efficiently whether $q \in K$. We consider this problem in an approximate setting. Given an approximation parameter $\varepsilon$, the query can be answered either way if the distance from $q$ to $K$'s boundary is at most $\varepsilon$ times $K$'s diameter. We assume that the dimension $d$ is fixed, and $K$ is presented as the intersection of $n$ halfspaces. Previous solutions to approximate polytope membership were based on straightforward applications of classic polytope approximation techniques by Dudley [ Approx. Theory, 10 (1974), pp. 227--236] and Bentley, Faust, and Preparata [ Commun. ACM, 25 (1982), pp. 64--68]. The former is optimal in the worst case with respect to space, and the latter is optimal with respect to query time. We present four main results. First, we show how to combine the two above techniques to obtain a simple space-time trade-off. Second, we present an algorithm that dramatically improves this trade-off. In particular, for any constant $\alpha \ge 4$, this data structure achieves query time roughly $O(1/\varepsilon^{(d-1)/\alpha})$ and space roughly $O(1/\varepsilon^{(d-1)(1 - \Omega(\log \alpha)/\alpha)})$. We do not know whether this space bound is tight, but our third result shows that there is a convex body such that our algorithm achieves a space of at least $\Omega( 1/\varepsilon^{(d-1)(1-O(\sqrt{\alpha})/\alpha} )$. Our fourth result shows that it is possible to reduce approximate Euclidean nearest neighbor searching to approximate polytope membership queries. Combined with the above results, this provides significant improvements to the best known space-time trade-offs for approximate nearest neighbor searching in $\mathbb{R}^d$. For example, we show that it is possible to achieve a query time of roughly $O(\log n + 1/\varepsilon^{d/4})$ with space roughly $O(n/\varepsilon^{d/4})$, thus reducing by half the exponent in the space bound.

The computation of (i) eps-kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In each case the input is a set of points in d-dimensional space for a constant d and an approximation parameter eps > 0. In this paper, we describe new algorithms for these problems, achieving significant improvements to the exponent of the eps-dependency in their running times, from roughly d to d/2 for the first two problems and from roughly d/3 to d/4 for problem (iii). These results are all based on an efficient decomposition of a convex body using a hierarchy of Macbeath regions, and contrast to previous solutions that decomposed the space using quadtrees and grids. By further application of these techniques, we also show that it is possible to obtain near-optimal preprocessing time for the most efficient data structures for (iv) approximate nearest neighbor searching, (v) directional width queries, and (vi) polytope membership queries.

In the polytope membership problem, a convex polytope K in ℝd is given, and the objective is to preprocess K into a data structure so that, given a query point q ∊ ℝd, it is possible to determine efficiently whether q ∊ K. We consider this problem in an approximate setting and assume that d is a constant. Given an approximation parameter ∊ > 0, the query can be answered either way if the distance from q to K's boundary is at most ∊ times K's diameter. Previous solutions to the problem were on the form of a space-time tradeoff, where logarithmic query time demands O(1/∊d-1) storage, whereas storage O(1/∊(d-1)/2) admits roughly O(1/∊(d-1)/8) query time. In this paper, we present a data structure that achieves logarithmic query time with storage of only O(1/∊(d-1)/2), which matches the worst-case lower bound on the complexity of any ∊- approximating polytope. Our data structure is based on a new technique, a hierarchy of ellipsoids defined as approximations to Macbeath regions. As an application, we obtain major improvements to approximate Euclidean nearest neighbor searching. Notably, the storage needed to answer ∊-approximate nearest neighbor queries for a set of n points in O(log n/∊) time is reduced to O(n/∊d/2). This halves the exponent in the ∊-dependency of the existing space bound of roughly O(n/∊d), which has stood for 15 years (HarPeled, 2001).

Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter $$\mathrm {diam}(K)$$ is given in Euclidean d-dimensional space, where d is a constant. Given an error parameter $$\varepsilon > 0$$ , the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most $$\varepsilon \cdot \mathrm {diam}(K)$$ . By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that $$O(1/\varepsilon ^{(d-1)/2})$$ facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is $$\widetilde{O}(1/\varepsilon ^{(d-1)/2})$$ , where $$\widetilde{O}$$ conceals a polylogarithmic factor in $$1/\varepsilon $$ . This is a significant improvement upon the best known bound, which is roughly $$O(1/\varepsilon ^{d-2})$$ . Our result is based on a novel combination of both old and new ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Bárány and Larman’s economical cap covering. Finally, we use a deterministic adaptation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.

Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter $diam(K)$ is given in Euclidean d-dimensional space, where $d$ is a constant. Given an error parameter eps > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most eps diam(K). By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that O(1/eps^{(d-1)/2}) facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is O-tilde(1/eps^{(d-1)/2}), where O-tilde conceals a polylogarithmic factor in 1/eps. This is an improvement upon the best known bound, which is roughly O(1/eps^{d-2}). Our result is based on a novel combination of both new and old ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Barany and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.

Approximating convex bodies is a fundamental question in geometry and has applications to a wide variety of optimization problems. Given a convex body K in REd for fixed d, the objective is to minimize the number of vertices or facets of an approximating polytope for a given Hausdorff error ε. The best known uniform bound, due to Dudley (1974), shows that O((diam(K)/ε)(d-1)/2) facets suffice. While this bound is optimal in the case of a Euclidean ball, it is far from optimal for skinny convex bodies. We show that, under the assumption that the width of the body in any direction is at least ε, it is possible to approximate a convex body using O(√area(K)/ε(d-1)/2) facets, where area(K) is the surface area of the body. This bound is never worse than the previous bound and may be significantly better for skinny bodies. This bound is provably optimal in the worst case and improves upon our earlier result (which appeared in SODA 2012).

The problem of approximating convex bodies by polytopes is an important and well studied problem. Given a convex body K in Rd, the objective is to minimize the number of vertices (alternatively the number of facets) of an approximating polytope for a given Hausdorff error ε. Results to date have been of two types. The first type assumes that K is smooth, and bounds hold in the limit as ε tends to zero. The second type requires no such assumptions. The latter type includes the well known results of Dudley (1974) and Bronshteyn and Ivanov (1976), which show that in spaces of fixed dimension, O((diam(K)/ε)(d − 1)/2) vertices (alt., facets) suffice. Our results are of this latter type. In our first result, under the assumption that the width of the body in any direction is at least ε, we strengthen the above bound to . This is never worse than the previous bound (by more than logarithmic factors) and may be significantly better for skinny bodies. Our analysis exploits an interesting analogy with a classical concept from the theory of convexity, called the Mahler volume. This is a dimensionless quantity that involves the product of the volumes of a convex body and its polar dual. In our second result, we apply the same machinery to improve upon the best known bounds for answering ε-approximate polytope membership queries. Given a convex polytope P defined as the intersection of halfspaces, such a query determines whether a query point q lies inside or outside P, but may return either answer if q's distance from P's boundary is at most ε. We show that, without increasing storage, it is possible to reduce the best known search times for ε-approximate polytope membership significantly. This further implies improvements to the best known search times for approximate nearest neighbor searching in spaces of fixed dimension.

We consider an approximate version of a fundamental geometric search problem, polytope membership queries. Given a convex polytope P in REd, presented as the intersection of halfspaces, the objective is to preprocess P so that, given a query point q, it is possible to determine efficiently whether q lies inside P subject to an error bound ε. Previous solutions to this problem were based on straightforward applications of classic polytope approximation techniques by Dudley (1974) and Bentley et al. (1982). The former yields minimum storage, and the latter yields constant query time. A space-time tradeoff can be obtained by interpolating between the two. We present the first significant improvements to this tradeoff. For example, using the same storage as Dudley, we reduce the query time from O(1/ε(d-1)/2) to O(1/ε(d-1)/4). Our approach is based on a very simple algorithm. Both lower bounds and upper bounds on the performance of the algorithm are presented.