Linear Crossing Families in Dense Point Sets

Definitions and mathematical statement

Let $n\ge 2$ be an integer and let $P\subset{\mathbb{R}}^2$ have cardinality $n$. With $\|\cdot\|_2$ denoting Euclidean distance, define \[ \delta(P)=\min_{p\ne q\in P}\|p-q\|_2, \qquad \operatorname{diam}(P)=\max_{p,q\in P}\|p-q\|_2. \] A segment spanned by $P$ is a closed straight segment $[a,b]$ with distinct endpoints $a,b\in P$. For this draft, two such segments cross properly if their supporting lines are distinct and their relative interiors intersect. A crossing family is a set of spanned segments any two distinct members of which cross properly. Thus shared endpoints and collinear overlaps do not count as crossings; concurrent proper crossings are permitted.

Question, with the asymptotic constants made explicit. Is it true that for every fixed real $C>0$ there exist a real $c=c(C)>0$ and an integer $n_0=n_0(C)\ge 2$ such that, for every integer $n\ge n_0$ and every set $P\subset{\mathbb{R}}^2$ satisfying \[ |P|=n,\qquad \delta(P)=1,\qquad \operatorname{diam}(P)\le C\sqrt n, \] there is a crossing family $\mathcal F$ of segments spanned by $P$ with \[ |\mathcal F|\ge cn? \] The dependence of $c$ and $n_0$ on the fixed diameter constant $C$ is the asymptotic interpretation used here; the source does not explicitly specify this dependence. The source also does not define crossing family or impose general position. The proper-crossing convention above therefore requires confirmation against the source, and no general-position hypothesis has been added. In particular, configurations with collinear points remain within the stated domain.

Short English statement

Must every sufficiently large planar point set with minimum separation exactly $1$ and diameter at most a fixed constant times $\sqrt n$ contain linearly many spanned segments that pairwise cross properly? The proposed linear constant may depend on the diameter constant. The crossing convention and any intended general-position assumptions require review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003474$, title Linear Crossing Families in Dense Point Sets, in Oberwolfach Reports Open Problems; exact source problem code catalogue entry. The record gives proposed year $2017$ and names no proposer.
• Supplied source citation: Discrete Geometry (2018), Oberwolfach Reports, pp. 1135--1205, DOI 10.4171/owr/2017/19. https://doi.org/10.4171/owr/2017/19. The background describes these reports as records of mathematical workshops and their open-problem discussions. The citation's year $2018$ and the DOI's $2017$ component are retained as supplied; their relationship has not been verified.
• Supplied literature source, labelled "Pach Rubin and Tardos on crossing segments": https://doi.org/10.1016/j.aim.2021.107779.
• Supplied literature source, labelled "Valtr on dense sets": https://archive.dimacs.rutgers.edu/TechnicalReports/TechReports/1994/94-55.html.
• Literature assessment dated exactly 2026-08-21: supplied dated curation, not independently verified. The record labels the problem partially solved and says the linear conjecture for dense point sets remains unsettled. It describes the improvement using the wording "from n to the n to the one minus epsilon scale" and also reports an $n^{1-o(1)}$ bound for general point sets. The former wording does not specify a coherent improvement or its quantifiers, so no precise intermediate bound is asserted here. The background explicitly calls this assessment dated literature triage derived from the supplied OWR curation and requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified; its accompanying explanation says that mathematical content was preserved while notation, typography, and sentence structure were repaired for publication. This supplied editorial label is not independent mathematical verification.