CS Paper Radar

The Deepest Pairs of Points Are Not as Deep as Conjectured

Herbert Edelsbrunner, Alexey Garber, Morteza Saghafian, Emo Welzl

cs.CG math.CO ·submitted 2026-11-14 20:15 UTC · v1
theory

Abstract

Given any finite set of points in $\mathbb{R}^2$, Neumann-Lara and Urrutia \cite{NLUr88} proved in 1988 that there is always a pair such that every circle through the two points encloses a positive fraction of all points. While Edelsbrunner et al.\ \cite{EHSS89} showed that the fraction is at least $\sfrac{1}{2} - \sfrac{1}{\sqrt{12}} = 0.211\ldots$, Urrutia \cite{Urr02} conjectured that the constant $\sfrac{1}{4} = 0.25$ in the upper bound proved by Hayward, Rappaport and Wenger \cite{HRW89} is best possible. We disprove this conjecture by lowering the constant to $\sfrac{3}{14} = 0.214\ldots$. The new bound also disproves a related conjecture by Ramos and Viaña \cite{RaVi09} on finite sets in convex position in $\mathbb{R}^3$. Finally, we generalize the latter extremal question to finite sets in possibly non-convex position, for which we prove the first linear lower bound, with constant $\sfrac{(2-\sqrt{2})}{6} = 0.097\ldots$.

Closest papers

Nearest neighbours by meaning across the whole index.

Containment Problems in Convex Sets

cs.CG cs.DMmath.CO ·2026-11-06 ·Prosenjit Bose, Bobby Miraftab, Tyler Tuttle
theory similarity 0.64
Abstract

Let $P$ be a set of $n$ points in the plane, and let $C$ be a compact, convex subset of the plane that contains the origin in its interior. We study the problem of finding two points $p$ and $q$ of $P$ with the property that any homothet of $C$ that contains $p$ and $q$ must contain at least a constant fraction of the points of $P$. We give proofs for several cases. When $C$ is strictly convex we achieve a fraction of $1/5$, and when $C$ is a general convex region we achieve a fraction of $1/6e$. We show how the ideas of this second bound can be used to prove a lower bound for a version of the problem in $\mathbb{R}^d$ when $C$ is a $d$-ball. We also consider a few special cases. When $C$ is a triangle we get a lower bound of $1/12$, and when we allow that triangle to be rotated by $π$ radians in addition to being scaled and translated we get a lower bound of $1/768$. In proving this last result, we improve the state of the art on the version of this problem in three dimensions, where $C$ is a parallelepiped. We also consider the algorithmic aspects of finding such a pair of points.

0.13

Holes in planar parallel sets: An integrated Betti-number bound and its pointwise failure

cs.CG math.AT ·2026-09-17 ·Tristan Guillaume
theory similarity 0.59
Abstract

Let A be a nonempty compact subset of the plane and let A (r) be its parallel set at distance r. We prove that the number of holes of A (r) the number of bounded components of its complement, which is its rst Betti number satises $\infty$ r 0 $β$1(A (r) ) dr $\le$ 4050 (diam A) 4 r -3 0 for every r0 > 0, the integrand vanishing for r $\ge$ diam A/ $\sqrt$ 3. The proof rests on Fu's theorem that the critical values of the distance function of a planar compact set form a set of vanishing half-dimensional Hausdor measure, on two lemmas of Rataj, Spodarev and Meschenmoser, and on a square-root summability estimate for the gaps of the critical-value set, of which we give a complete proof. We show by an explicit family of curves two combs facing each other that no analogous bound can hold at a xed radius: a connected curve of bounded length, diameter, oscillation count, parallel-set area and parallel-set perimeter can have arbitrarily many holes at one radius, so the integrated estimate cannot be replaced by a xed-radius bound in terms of these coarse geometric quantities. We also bound the hole count uniformly in the radius by the number of components of local maxima of the distance function, and record a bound on the boundary length of a parallel set by its area. The results supply the deterministic input for limit theorems on the persistent homology of the Wiener sausage.

0.44

Breaking the Infinite Barrier in the $\frac{1}{3}$--$\frac{2}{3}$ Conjecture

cs.DM math.CO ·2026-09-25 ·Max Aires, Swee Hong Chan, Igor Pak, Greta Panova
similarity 0.56
Abstract · 32 pages, v2 simplifies the proof of Lemmas 4.2 and 6.4

The balance constant is a poset parameter measuring how well random linear extensions can be split according to their relative order on two elements. We give an $\varepsilon$-improvement for the balance constant over the bound by Brightwell, Felsner and Trotter (1995), for some small $\varepsilon>0$. This is the first general result towards the $\frac{1}{3}$--$\frac{2}{3}$ conjecture in over 30 years.

0.35

Discrepancy of geometric incidences

cs.CC math.COcs.DMmath.MG ·2026-08-28 ·Azem Adibelli, István Tomon
theory similarity 0.55
Abstract · 32 pages, 1 figure

We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tildeΩ(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.

0.40

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.54
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

On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets

cs.CG ·2026-08-10 ·Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari, Bobby Miraftab, Michiel Smid +1 more
theory similarity 0.54
Abstract

The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an earlier one. Its spanning ratio is known to be bounded by a universal constant, but the standard bound obtained from the diamond and good-polygon properties is about $11739.1$. We prove a substantially smaller bound for points in convex position. In particular, for every finite point set $P\subset\mathbb{R}^2$ in convex position and every pair $u,v\in P$, the greedy triangulation contains a $u$--$v$ path of length at most $κ|uv|$, where $κ<17.814$. Thus, the greedy triangulation of a convex point set is an $18$-spanner.

0.04

Optimal Configurations for Mordell's Problem

cs.SC math.COmath.OC ·2026-11-02 ·Xiang Ji, Tiancheng Xu, Wensheng Yu
theoryunusual similarity 0.54
Abstract

Mordell's problem asks for the largest product of squared pairwise distances among $n$ points in the complex plane with a prescribed sum of squared distances from the origin. When this sum equals $n$, the maximum for $2\le n\le5$ is known to be $n^n$, attained precisely by the $n$th roots of unity up to rotation and relabeling. For $n\ge6$, Chalk showed that a regular polygon together with its center gives a larger product than the regular $n$-gon. We prove that for $6\le n\le9$ the maximum is $(n-1)^{n-1}r_n^{n(n-1)}$, where $r_n=\sqrt{n/(n-1)}$. Up to the same symmetries, the unique maximizer consists of the origin and the vertices of a regular $(n-1)$-gon of radius $r_n$. For six points, algebraic elimination reduces the proof to an exact comparison of stationary values. For seven points, we compare all twelve classes in a published classification of equilibria. For eight and nine points, rigorous interval arithmetic establishes an inequality for every admissible pair. Summing over pairs gives the sharp global bound, and the equality conditions determine the configuration. An explicit ten-point comparison and a known instability result together exclude Chalk's configuration for every $n\ge10$. For each $n$ from two through eight, Mordell's problem and the minimum-diameter problem studied by Bateman and Erdős have a common optimal configuration.

0.29

New lower bounds for kissing numbers in dimensions 32-35 and 37-39

cs.DM math.MGcs.ITmath.CO ·2026-10-22 ·Qihong Lin
code/data similarity 0.54
Abstract · 8 pages. Certificates and verification programs: https://github.com/QH-Lin/kissing-number-32 (doi:10.5281/zenodo.23527725) and https://githu…

We show that the kissing numbers in dimensions 32, 33, 34, 35, 37, 38 and 39 are at least 352320, 370240, 390980, 415308, 499816, 605322 and 768916, improving the previous bounds 347584, 364736, 384836, 409676, 498024, 591900 and 763668. Except in dimension 38, the configurations are those of Edel, Rains and Sloane with new binary constant-weight codes of weight 8 and minimum distance 8 in the middle layer; each additional word adds 128 points. In dimension 38 we add 6855 antipodal pairs of vectors of the second shell of the Leech lattice to the empty equator of Kravatskiy's 591612-point configuration, where 144 pairs were known; this is an independent set problem in a regular graph of degree 11178 on 8386560 vertices. The codes and lines were found by local search, and all configurations were checked pair by pair in exact integer arithmetic.

0.40