Acute Sets In Euclidean Spaces
Viktor Harangi · SIAM Journal on Discrete Mathematics · 2011
A finite set [Formula: see text] in [Formula: see text] is called an acute set if any angle determined by three points of [Formula: see text] is acute. We examine the maximal cardinality [Formula: see text] of a [Formula: see text]-dimensional acute set. The exact value of [Formula: see text] is known only for [Formula: see text]. For each [Formula: see text] we improve on the best known lower bound for [Formula: see text]. We present different approaches. On one hand, we give a probabilistic proof that [Formula: see text]. (This improves a random construction given by Erdo˝s and Füredi.) On the other hand, we give an almost exponential constructive example which outdoes the random construction in low dimension ([Formula: see text]). Both approaches use the small dimensional examples that we found partly by hand ([Formula: see text], 5) and partly by computer ([Formula: see text]). We also investigate the following variant of the above problem: what is the maximal size [Formula: see text] of a [Formula: see text]-dimensional cubic acute set (that is, an acute set contained in the vertex set of a [Formula: see text]-dimensional hypercube)? We give an almost exponential constructive lower bound, and we improve on the best known upper bound.