Papers for
geometric algorithm designers
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Union volume calculation of translated convex shapes differs by dimension
Union of Translates of a Convex Body
Abstract: We consider the problem of calculating the volume of the union of translates of a strictly convex body $K\subset\mathbb{R}^d$. When $K$ is a ball, it is possible to simplify the inclusion-exclusion formula by summing over only a small subset of all terms. This subset corresponds to intersecting cells in the Voronoi diagram of the ball centers. We prove that the same simplification is valid for every strictly convex $K$ if and only if $d\leq 2$. Moreover, in three dimensions and when $K$ is $C^4$, we use the Fubini-Pick affine invariant to show that the topological identity underlying this technique holds if and only if $K$ is an ellipsoid.
Packing tiny reciprocal rectangles into matching squares is possible late in the sequence
Packing Tails of Reciprocal Rectangles into Squares of Equal Area
Abstract: The Meir--Moser rectangle-packing problem asks whether all rectangles with side lengths \(1/n\) and \(1/(n+1)\), for \(n\ge1\), can be packed into the unit square with pairwise disjoint interiors. We establish a tail version of this problem. Let \(R_n\) denote the rectangle with these side lengths. We prove that there exists an integer \(m_0\) such that, for every \(m\ge m_0\), the family \(\{R_n:n\ge m\}\) admits a packing, by translations and right-angle rotations, into a square of side length \(m^{-1/2}\), with pairwise disjoint interiors. The area of the square equals the sum of the areas of all the rectangles. The geometric construction recursively decomposes rectangular gaps, while local randomized quotas and random permutations assign subsequent integer indices. We separately control the total area of waiting gaps and the assignment load at each index. The proof is organized in six steps: a finite-prefix reduction, geometric row decompositions, an area bootstrap, a sharp source-load estimate, control of the actual adaptive construction, and a compactness limit. For every finite time horizon, the probability of failure has a bound that is independent of the horizon and can be made arbitrarily small. The adaptive step uses a permanent load ledger, actual fresh height queries, and a one-sided comparison with a frozen source experiment. Compactness then yields an infinite packing. The final packing statements have been checked in Lean 4. A sufficient threshold is \(m_0=10^{1000}\). This result applies only to sufficiently late tails and does not resolve the original Meir--Moser rectangle-packing problem for the full sequence starting at \(n=1\), which remains open.