Paper proves O(k log n log log n) directions determine point multisets in any dimension
Original title: How many sorted projections determine n points in k dimensions?
Theoretical result shows nearly logarithmic projections suffice to uniquely determine multisets of n points in k dimensions.
The paper proves that almost every choice of O(k log n log log n) directions suffices to determine every multiset of n points via sorted projections in any dimension. This improves on the linear bound of (k-1)n+1 and uses two lemmas from list recovery of random linear codes. It also shows 2k-1 directions never determine three points and improves plane bounds to O(1.78^m) failing pairs.
- O(k log n log log n) directions suffice uniformly in k and n
- 2k-1 directions never determine three points
- Every m directions fail on some pair of multisets of size O(1.78^m) in the plane
- (4k-2)ln(2n)ln(k log_2 2n)+k+1 directions suffice in general position
From the original article
1 min read at arxiv.orgLet $d_1,\dots,d_m$ be directions in $\mathbb{R}^k$, where $k\ge 2$. A multiset $X$ of $n$ points of $\mathbb{R}^k$ projects to the $m$ multisets of numbers $\{\{x\cdot d_j : x\in X\}\}$, or equivalently to the $m$ sorted lists of these numbers. How many directions are needed for these projections to determine every multiset of $n$ points?
By Christopher Gorham Lester · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.