CS Paper Radar

A 0.41275 lower bound for the three-dimensional Blaschke-Lebesgue problem

Yunjiang Jiang

cs.CG math.MG ·submitted 2026-09-08 06:19 UTC · v1
theory

Abstract

We prove that every convex body $K\subset\mathbb{R}^3$ of constant width $w>0$ satisfies \[ \operatorname{Vol}(K)\ge \frac{1651}{4000}w^3=0.41275\,w^3. \] This improves the certified lower bound $0.411040473721188\ldots\,w^3$ announced by Hyra and the earlier spectral bound $4πw^3/33$ of Nishioka. The main new ingredient is a contact-tetrahedron estimate near equality in Jung's circumradius inequality. Four balanced contacts of a minimum circumscribed ball form a near-regular tetrahedron; constant width then forces, beyond the tetrahedron itself, spherical regions over its faces, spindle sectors along its edges, and additional face-edge sectors. These regions can be selected with pairwise disjoint interiors and quantified by the total squared-edge deficit. A sharp convexity argument relates that deficit to the circumradius, and a symmetrization argument controls the four face contributions with only quadratic loss. This gives the analytic bound $\operatorname{Vol}(K)>0.41275318$ near the Jung endpoint. For the complementary circumradius range we use Hyra's radial transport/tangent-majorant mechanism together with closed-form contact and antipodal profiles. The antipodal contribution has an elementary primitive. For the contact contribution, a second-order concavity estimate converts the angular Jacobian into an explicit rational lower density; that density is monotone in the circumradius. The whole intermediate range therefore reduces to a single endpoint calculation, giving $\operatorname{Vol}(K)>0.41275168$. For smaller circumradius the tangent-majorant inequality with its nonnegative gap discarded already gives $\operatorname{Vol}(K)>0.41308109$. The proof is entirely analytic and requires no computer-assisted certificate.

Closest papers

Nearest neighbours by meaning across the whole index.

On the weighted hard-core model and Rado's covering problem for congruent Euclidean balls

cs.DM math.MGmath.CAmath.CO+1 ·2026-08-10 ·Chengfei Xie, Gennian Ge
theory similarity 0.58
Abstract · 17 pages; any comments are welcome

Let $K$ be a symmetric convex body in $\mathbb{R}^d$ and let $f(K)$ denote the largest constant $c$ such that every finite collection of translates of $K$ contains a pairwise disjoint subcollection whose total volume is at least $c$ times the volume of the union of the original collection. The classical Vitali covering lemma gives $f(K)\geq3^{-d}$. In this paper, we establish two improvements. First, by a purely combinatorial argument, we prove that $$ f(K)\geq \frac{2}{3^d + 2^d} $$ for every symmetric convex body $K$. This improves the Vitali bound by a factor tending to $2$ as $d$ tends to infinity. Second, using a weighted hard-core model together with a weighted geometric estimate for intersections of Euclidean balls, we show that, for all sufficiently large $d$, $$ f(B^d)\geq \left( \log\frac{3}{1+\sqrt3} -O\left(\frac{\log d}{d}\right) \right)d\,3^{-d}, $$ where $B^d$ is the unit Euclidean ball in $\mathbb{R}^d$. Thus, the classical lower bound is improved by a factor of order $d$.

0.38

Curves of constant width and Lebesgue's covering problem

cs.CG math.MG ·2026-08-31 ·Ujjwal Mishra
theory similarity 0.56
Abstract

A universal cover is a convex set in the plane that contains a congruent copy of every planar set of diameter one. Lebesgue asked in 1914 for one of least area, and the value is not known. We prove that every convex universal cover has area at least 0.8344, improving on 0.832, published in 2005, and 0.833, in a 2026 preprint, both of which come from a disc together with an equilateral triangle and a regular pentagon. Our test sets are instead curves of constant width: the disc, the Reuleaux triangle and the Reuleaux pentagon. Each contains the regular polygon it is built on, so the family is strictly larger at the same number of bodies and the same number of placement parameters, and we show that the classical configuration admits an arrangement whose hull has area below 0.8336, so no bound drawn from those three sets by this argument reaches ours. Curves of constant width were proposed for this role, and explored numerically, by Gibbs in 2014; what is added here is a proof. It consists of an analytic reduction followed by one finite computation. The reduction bounds the hull area from below over an entire box of placements at once, by eroding each Reuleaux polygon to a fixed set contained in every placement that box allows. The computation is an exhaustive subdivision of the resulting five-dimensional space, recorded as a certificate of 486,799,600 nodes and checked by a verifier independent of the search, with a rigorous bound on its floating point error some thousands of times smaller than the margin the verification attains.

0.16

New lower bounds for kissing numbers in dimensions $25$--$31$

cs.IT ·2026-09-18 ·Rustem Takhanov, Stanislav Yun
similarity 0.55
Abstract

The kissing number in dimension $d$ is the largest number of non-overlapping congruent spheres that can simultaneously touch a central sphere of the same size. We study dimensions $25$-$31$, where the best previous constructions are based on Leech lifting from the optimal kissing configuration in dimension $24$. Our method exploits the absence of contacts between the unlifted bulk and the block consisting of lifted and auxiliary vectors. Rotating this block while keeping the bulk fixed creates room for two antipodal points in dimensions $26$, $27$, and $28$, and one point in dimension $29$. Three further modifications yield improvements in dimensions $25$, $30$ and $31$: (a) a nonorthogonal diagonal linear deformation of the lifted block admits two antipodal points in dimension $25$; (b) rotating the additional coordinates of the lifted vectors and then applying a small orthogonal transformation to the resulting lifted block as a whole admits two antipodal points in dimension $30$; (c) rotating only the additional coordinates of the lifted vectors admits four nonantipodal points in dimension $31$. Together, these constructions yield the new lower bounds $τ_{25}\geq 197058$, $τ_{26}\geq 198552$, $τ_{27}\geq 200046$, $τ_{28}\geq 204522$, $τ_{29}\geq 209497$, $τ_{30}\ge 220442$, and $τ_{31}\geq 238354$.

0.42

Almost Empty Monochromatic Polygons in Planar Point Sets

cs.CG math.COcs.DM ·2026-10-05 ·Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
publishedtheory similarity 0.55
Abstract · 28 pages, 9 figures

For integers $r \ge 3$, $c \ge 2$, and $s \ge 0$, let $\mathsf{M}_r^{\star}(c,s)$ denote the smallest integer such that any set of at least $\mathsf{M}_r^{\star}(c,s)$ points in the plane in general position (no three on a line), colored with $c$ colors, contains a monochromatic $r$-gon (not necessarily convex) with at most $s$ interior points. Define $λ_r^{\star}(c)$ to be the smallest integer such that $\mathsf{M}_r^{\star}(c,λ_r^{\star}(c)) < \infty$. The case of triangles, that is, $r=3$, has been studied in recent years. In this paper, we establish bounds on $λ_r^{\star}(c)$, for $r \ge 4$. Specifically, in the bichromatic case, we prove that $λ_r^{\star}(2)\leq \lfloor\frac{r-2}{2}\rfloor$, for every $r\geq3$. For hexagons, we sharpen this bound to $λ_6^{\star}(2)\leq1$, that is, every sufficiently large bichromatic planar point set in general position contains a monochromatic hexagon with at most one interior point. Next, for any number of colors $c\geq3$ and $r\geq3$, we show that $$(r - 2) \left \lfloor \frac{c-1}{2} \right \rfloor \leq λ_r^\star(c) \leq (r-2)(c-2)+\left\lfloor(r-2)δ_c\right\rfloor, $$ for some constant $δ_c \in (0, \frac{1}{2}]$, depending on $c$. The upper bounds combine spiral polygonizations with nested convex-hull arguments and, in the hexagon case, incidence counting in $4$-connected triangulations. The lower bounds follow from colored Horton-set constructions.

0.45

Polylogarithmic Approximation for Packing Convex Polyhedra

cs.CG cs.DS ·2026-11-19 ·Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae
theoryhot direction similarity 0.54
Abstract · 28 pages, 8 figures

We study translational packing of convex polyhedra in three dimensions. Given $n$ convex polyhedra in $\mathbb{R}^3$, we seek a placement with pairwise disjoint interiors that minimizes the volume of an axis-parallel bounding box. Constant-factor approximation algorithms are known when rotations are allowed, but no approximation guarantee was previously known for arbitrary convex polyhedra with fixed orientations. A central difficulty is that, unlike in the plane, the total volume and the coordinate extents of the objects do not provide a useful lower bound on the optimum: even objects with small total volume and small diameter may require a container of large volume. We overcome this difficulty using a better geometric lower bound based on a surprising connection to Wang and Zahl's celebrated recent proof of the three-dimensional Kakeya conjecture. Using this, we obtain a polynomial-time $n^{o(1)}$-approximation algorithm. A recent strengthening of Wang and Zahl's theorem claimed by OpenAI gives a polylogarithmic approximation ratio for the same algorithm. Our ideas extend to bin and strip packing: for any fixed $δ>0$, we obtain the same approximation guarantees for translational packing of convex polyhedra whose coordinate widths are at most a $1-δ$ fraction of the corresponding container widths.

0.35

Improved bounds for universal convex covers of unit arcs

cs.CG math.MG ·2026-09-18 ·Ethan Keller
theorycode/data similarity 0.54
Abstract · 22 pages, 9 figures. Lean 4 formalization, code, and certificates available at https://github.com/ethan-keller/moser-worm-improved-bounds

Moser's worm problem asks for a planar region of least area containing a congruent copy of every unit arc. We show that the infimum area $α$ among convex universal covers satisfies $0.239\leα\le0.24633\ldots$, reducing the gap between the previous refereed bounds by over $75\%$. For the lower bound, we choose four unit polygonal arcs and prove by finite subdivision that, however they are placed, their convex hull has area at least $0.239$. For the upper bound, we construct a quadrilateral of area $0.24633\ldots$ and prove cover universality by showing that its support inequalities force uncovered arcs to have length greater than one. The full proof is formalized in Lean 4 and verified by the Lean kernel. Code and certificates are available at https://github.com/ethan-keller/moser-worm-improved-bounds.

0.48

Near-Optimal Oracle Bounds for Isotropic Rounding

cs.DS ·2026-10-05 ·Yang P. Liu, Richard Peng, Alicia Stepin, Colin Tang
theoryhighly cited similarity 0.53
Abstract

We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B(0,r)\subseteq K\subseteq B(0,R)$ in $\R^n$ can be rounded using $\Ot(n^3)$ membership queries; the upper bound extends to logconcave distributions. We prove a matching $\Omegat(n^3)$ lower bound, even when $R/r=n^{O(1)}$. The key lemma states that if $B(0,1)\subseteq K$ and $\Cov(\Unif(K))\preceqκI_n$, with $κ\ge1$, then approximate uniform sampling from an initial density bounded by a constant times the uniform density uses $\Ot(n^2\sqrtκ)$ expected membership queries. We prove this by simulating reflected kinetic dynamics using the analysis of Eberle and Lörler~\cite{EL26:journal}. Combining this sampler with the ideas of Jia, Laddha, Lee, and Vempala~\cite{JLLV26:journal} for rounding well-rounded bodies yields our $\Ot(n^3)$ query rounding algorithm. We also give a counterexample to an ellipsoid-growth conjecture from previous papers on this topic.

0.50

Almost Empty Monochromatic Triangles With Many Colors

cs.CG math.CO ·2026-09-11 ·Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
theory similarity 0.53
Abstract · 13 pages, 1 figure

Given integers $c\geq 2$ and $s\geq 0$, let $\mathsf{M}_3(c,s)$ denote the least integer such that every set of at least $\mathsf{M}_3(c,s)$ points in the plane, no three on a line, colored with $c$ colors, contains a monochromatic triangle with at most $s$ interior points. Further, let $λ_3(c)$ be the least integer such that $\mathsf{M}_3(c,λ_3(c))<\infty$. \citet{colorempty} proved that, for every $c\geq 2$, $$\left\lfloor\frac{c-1}{2}\right\rfloor \leq λ_3(c)\leq c-2.$$ Later, \citet{cravioto2019almost} improved the upper bound to $c-3$, for $c\geq 4$. In this paper, we refine their argument to obtain the following asymptotic improvement: $$λ_3(c) \leq c-\sqrt{c\log c}+o (\sqrt{c\log c} ),$$ for all sufficiently large $c$. We also show that every $c$-coloring of a sufficiently large Horton set contains a monochromatic triangle with at most $\lfloor \frac{c-1}{2} \rfloor$ interior points. This shows that the aforementioned lower bound on $λ_3(c)$ is sharp within the class of Horton sets. We conclude with a conjecture on the large-color asymptotics of $λ_3(c)$.

0.45