Given a set $S\_n$ of $n$ points $\mathbf{x}\_1, \mathbf{x}\_2, \ldots, \mathbf{x}\_n\in\mathbb{R}^d$, such that every $(d+1)$-tuple in $S\_n$ is affinely independent, and let $C(S\_n)$ be the convex hull of the points of $S$. Let now $T(S\_n)$ be the set of all triplets $\{\mathbf{x}\_i, \mathbf{x}\_j, \mathbf{x}\_k\}$ of points in $S\_n$ for all $1\le i<j<k\le n$ such that no point of each triangle having $\mathbf{x}\_i, \mathbf{x}\_j, \mathbf{x}\_k$ as vertices, is an interior point of $C(S\_n)$.




---


**Question:** What is the maximum cardinality $m(n,d)$ of $T$ over all possible sets $S\_n$ of $n$ points in $\mathbb{R}^d$?



Triangles and convex hulls in high dimensions
A $3$-[neighborly polytope](https://en.wikipedia.org/wiki/Neighborly_polytope)
is one in which every triple of vertices forms a face.
Such $k$-neighborly polytopes exist and achieve the
maximum number of $k$-faces,
by the [upper bound theorem of McMullen](https://en.wikipedia.org/wiki/Upper_bound_theorem).


So your maximum bound is $\binom{n}{3}=O(n^3)$, as Neil Strickland suggests.


