login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A347941 For sets of n random points in the real plane, a(n) is an upper bound for the minimal number of nearest neighbors. 1
2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22, 22, 22, 23 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,1

COMMENTS

The sequence deals with sets of n points with pairwise different distances. The randomness in the definition provides for pairwise different distances with probability = 1.

A point A is called a nearest neighbor if there is a point B with smaller distance to A than to any other point C.

In graph theory terms: Let G be a simple digraph; the vertices of G are n arbitrarily placed points in R^2 with pairwise different distances; the edges of G are arrows joining each point (tail end) to its nearest neighbor (head end). Let b(n) be the minimal number of points receiving arrowheads in any such graph. a(n) is the best upper bound yet known for b(n).

A261953(n) for n >= 2 can be seen as an "inverse" to a(n).

a(n) is built by constructing G with n points and m nearest neighbors, m chosen as minimal as possible, then defining a(n)=m.

The start is a(n)=2 for n <= 9 and a(n)=3 for n=10,11,12. We call the pairs (n,m)=(9,2) and (n,m)=(12,3) "anchor pairs" and proceed to bigger n by combining graphs with these anchor pairs to bigger graphs. So the next anchor pairs are (18,4), (21,5) and (27,6).

If (n0,m-1) and (n1,m) are anchor pairs then a(n')=m for n0 < n' <= n1.

We conjecture that a(n) is optimal. This claim is true if the following assumptions hold:

- The anchor pairs (9,2) and (12,3) are optimal.

- All bigger anchor pairs (n,m) are constructed by combining copies of (9,2) if m is even and adding one (12,3) if m is odd.

LINKS

Table of n, a(n) for n=2..100.

Manfred Boergens, Next-neighbours

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,1,-1).

FORMULA

a(2) = a(3) = 2.

a(n) = 2j for n = 9j-5 ... 9j, j > 0;

a(n) = 2j+1 for n = 9j+1 ... 9j+3, j > 0;

With h=(n+5)/9 for n>3:

a(n) = 2*floor(h) if h-floor(h)<2/3;

a(n) = 2*floor(h)+1 otherwise.

G.f.: -x^2*(x^11-2*x^9+x^8+2)/(-x^10+x^9+x-1). - Alois P. Heinz, Sep 20 2021

EXAMPLE

G with 25 vertices has at least 6 nearest neighbors (conjectured; it is proved that there are G with n=25 and m=6 but it is not yet proved that 6 is the minimum).

MATHEMATICA

h=(n+5)/9; Join[{2, 2}, Table[2 Floor[h] + If[FractionalPart[h]<2/3, 0, 1], {n, 4, 100}]]

CROSSREFS

Cf. A261953.

Sequence in context: A072746 A179528 A105390 * A013941 A061798 A345206

Adjacent sequences:  A347938 A347939 A347940 * A347942 A347943 A347944

KEYWORD

nonn,easy

AUTHOR

Manfred Boergens, Sep 20 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 5 05:47 EDT 2022. Contains 355087 sequences. (Running on oeis4.)