1
$\begingroup$

In $\mathbb{R}^n$ consider three points $v_i$. Here at $v_2$ the angle $\angle v_1v_2v_3$ is acute if it is strictly smaller then $\frac{\pi}{2}$.

Note that in $\mathbb{R}^2$, one can find three points such that

all angles are acute.

For example, an equilateral triangle.

But there are no $4$ point satisfying such property.

Taking a regular tetrahedron in $\mathbb{R}^3$, we have $4$ points satisfying such a property.

Hence can we conclude that the maximum number of points in $\mathbb{R}^n$ with the above angle property is equal to or smaller than $n+1$?

Is this right ? Thank you in advance.

$\endgroup$
3

5 Answers 5

3
$\begingroup$

We will say that a set on $N$ points has the Acute Angle Configuration (AAC) if all the angles that can be formed with 3 points among them are acute;

First of all, here is a very readable reference that brings additional information to the reference given by @Théophile: Sets of points determining only acute angles and some related colouring problems by David Bevan:

oro.open.ac.uk/33661/1/Acute.pdf

with the very interesting arrays that can be found in page 9 and that I reproduce here: enter image description here

On my side, I have written the following Matlab program that makes random searches in $\mathbb{R}^D$ for $N$ AAC points.

clear all;
N=5;D=3;
b=nchoosek(N,3);%total number of triangles
I=nchoosek(1:N,3);
G=0;
Ns=10000;
for k=1:Ns;
  P=rand(N,D);
  T=[];
  for p=1:b 
     J=I(p,:);
     A=P(J(1),:);B=P(J(2),:);C=P(J(3),:);%triangle
     U=A-B;V=B-C;W=C-A; % its vectorialized sides
     T=[T,-U*W',-U*V',-V*W']; % dot products of these vectors
  end;
  if all(T>0) 
     P
     G=G+1;
  end;
end;
G/Ns %percentage of hits (successes)

For example, finding 5 AAC points in $\mathbb{R^3}$ has necessitated a rather long execution time, meaning that such a configuration "at the limit" is exceptional:

$$\begin{array}{lll} (0.6842, \ \ & 0.2992, \ \ & 0.7554)\\ (0.2169, \ \ & 0.0480, \ \ & 0.2551)\\ (0.6766, \ \ & 0.1850, \ \ & 0.1968)\\ (0.2088, \ \ & 0.3158, \ \ & 0.7579)\\ (0.4731, \ \ & 0.8037, \ \ & 0.0771) \end{array}$$

To my own surprise, I have, with this program, found almost instantly a solution with $N=6$ and $D=5$ which is:

$$\begin{array}{lll} 0, & \ 0, & \ 1, & 0, & \ 0 \\ 1, & \ 1, & \ 0, & \ 0, & \ 1\\ 1, & \ 1, & \ 1, & \ 1, & \ 0\\ 1, & \ 0, & \ 0, & \ 1, & \ 1\\ 0, & \ 1, & \ 0, & \ 1, & \ 0 \\ 0, & \ 1, & \ 1, & \ 1, & \ 1 \end{array}$$

enter image description here

For example, for $\mathbb{R}^D=\mathbb{R}^{11}$, the Matlab program finds the following $N=12$ AAC points, proving that $\kappa(11) \geq 12$.

$$\begin{array}{rrrrrrrrrrr} (836, \ \ 807, \ \ 929, \ \ 118, \ \ 242, \ \ 354, \ \ 125,\ \ 178, \ \ 310, \ \ 631, \ \ 2)\\ (73, \ \ 687, \ \ 470, \ \ 40, \ \ 163, \ \ 466, \ \ 782, \ \ 788, \ \ 493, \ \ 314, \ \ 777) \\ (248, \ \ 279, \ \ 666, \ \ 485, \ \ 574, \ \ 477, \ \ 883, \ \ 663, \ \ 24, \ \ 270, \ \ 299) \\ (738, \ \ 742, \ \ 563, \ \ 869, \ \ 304, \ \ 786, \ \ 517, \ \ 855, \ \ 586, \ \ 871, \ \ 28) \\ (982, \ \ 823, \ \ 731, \ \ 297, \ \ 880, \ \ 936, \ \ 355, \ \ 672, \ \ 779, \ \ 796, \ \ 76) \\ (335, \ \ 395, \ \ 900, \ \ 148, \ \ 527, \ \ 240, \ \ 981, \ \ 727, \ \ 923, \ \ 97, \ \ 655) \\ (283, \ \ 663, \ \ 937, \ \ 309, \ \ 617, \ \ 812, \ \ 247, \ \ 478, \ \ 896, \ \ 729, \ \ 866) \\ (604, \ \ 466, \ \ 248, \ \ 349, \ \ 754, \ \ 834, \ \ 862, \ \ 937, \ \ 531, \ \ 75, \ \ 582) \\ (410, \ \ 750, \ \ 299, \ \ 145, \ \ 483, \ \ 147, \ \ 176, \ \ 890, \ \ 749, \ \ 584, \ \ 56) \\ (973, \ \ 155, \ \ 541, \ \ 567, \ \ 102, \ \ 452, \ \ 471, \ \ 327 , \ \ 458, \ \ 832, \ \ 406) \\ (807, \ \ 575, \ \ 745, \ \ 158, \ \ 719, \ \ 881, \ \ 489, \ \ 960, \ \ 7, \ \ 836, \ \ 583) \\ (348, \ \ 181, \ \ 22, \ \ 207, \ \ 540, \ \ 773, \ \ 193, \ \ 90, \ \ 856, \ \ 837, \ \ 441). \end{array}$$

$\endgroup$
3
  • $\begingroup$ Now, I think that I my answer is "stabilized" around the very good article by David Bevan. As often, the information is there, but we have not the good keywords... or we are impatient to work by ourselves... Could you give me your opinion about this answer ? $\endgroup$
    – Jean Marie
    May 10, 2017 at 9:11
  • $\begingroup$ Thank you for your concern. And by an article you said I realized that five points in $\mathbb{R}^3$ is possible and it is largest. $\endgroup$
    – HK Lee
    May 10, 2017 at 15:45
  • $\begingroup$ Thanks for calling attention to a very interesting issue. Sorry for the many errors I did at first. $\endgroup$
    – Jean Marie
    May 10, 2017 at 15:47
3
$\begingroup$

An arxiv.org preprint by D. Zakharov proves that in $\mathbb{R}^n$ there is a set of at least $\sqrt{2}^{n+1.64}$ points, and a follow-up proves that there is a set of at least $\left(\frac{1+\sqrt 5}{2}\right)^n$ points.

$\endgroup$
0
2
$\begingroup$

I don't think it's reasonable to make such a conjecture based on two examples (and in fact there is a set of $5$ points in $\Bbb R^3$, so the tetrahedron is not a maximal example).

An article by Erdős and Füredi called The Greatest Angle Among $n$ Points in the $d$-Dimensional Euclidean Space shows that there is a set of at least $1.15^d$ points in $\Bbb R^d$ satisfying the given property.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. And can you introduce such five points in $\mathbb{R}^3$ ? $\endgroup$
    – HK Lee
    May 10, 2017 at 2:15
1
$\begingroup$

There have been significant advances in this problem: math.stackexchange.com/questions/2363546/tight-acute-sets

$\endgroup$
1
$\begingroup$

I have new lower bounds for the case when the points lie in {0,1}^n. Please see this: https://oeis.org/A089676

$\endgroup$
1
  • $\begingroup$ When you have such small answers, as this one and the previous one on the same subject, you should group them by adding an "edit" to the first answer. $\endgroup$
    – Jean Marie
    Mar 26, 2018 at 22:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .