# Maximum number of simplexes given n-element point sets in the plane

Does anyone know if it has been proved what the maximum number of simplexes occurring in the plane is for a given value of $n$ points? I am interested in this question in relation to packing problems (eventually generalizing to tetrahedron packing in 3-space).

In 1974, Harborth proved the following theorem by applying Euler's polyhedral formula and using induction.

Let $f_{2}^{\text{min}}(n)$ denote the maximum number of times the minimum distance can occur among n points in the plane. Then, $$f_{2}^{\text{min}}(n) = \lfloor 3n - \sqrt{12n -3} \rfloor$$

For any dimension $d$, we have a general definition for the maximum number of times the minimum distance can occur among $n$ points in $\mathbb{R}^d$ as, $$f_{d}^{\text{min}}(n) = \max_{|P|=n} | \{\overline{pq} | p,q \in P \text{ and } |p-q|=1\}|$$ where $P \subseteq \mathbb{R}^d$ is any $n$-element point set. We now wish to extend this result to not only consider the maximum number of times the minimum distance can occur among $n$ points in $\mathbb{R}^d$, but to the maximum number of times a regular $k$-simplex of minimum side length can occur among $n$ points in $\mathbb{R}^d$.

Toward the end, I define the $\Delta$-function as follows:

Let $\widehat{v_{1}...v_{k}}$ denote a $k$-simplex with vertices $v_{1},...,v_{k} \in \mathbb{R}^d$. Then, $$\Delta_{d}^{k}(n) = \max_{|P|=n} | \{\widehat{v_{1}...v_{k}} | v_{1},...,v_{k} \in P, |v_{i}-v_{j}|=1, i\neq j\}|$$ defines the maximum number of occurrences of a regular $k$-simplex of minimum edge length determined by an $n$-element point set in $P \subseteq \mathbb{R}^d$.

So, in terms of this $\Delta$-function, we have $f_{2}^{\text{min}}(n) = \Delta_{2}^{1}(n) = \lfloor 3n - \sqrt{12n -3} \rfloor$. I am now interested in extending Harborth's result to $\Delta_{2}^{2}(n)$ and in doing so I have proved the following corollary of two lemmas I proved (I will not mention the proofs).

Any simplicial $k$-complex $\mathcal{K}$ for which $\Delta_{d}^{k}(n)=|\mathcal{K}|$ is connected and homogeneous, where $k \leq d$ for $P \subseteq \mathbb{R}^d$ with $|P|=n$.

I now want to extend Harborth's result to determining $\Delta_{2}^{2}(n)$, that is, determining the maximum number of regular triangles of side length equal to the minimum distance that can occur among an $n$-element point set in the plane.

The start of my proof looks something like this, I am stuck though and am looking for guidance.

By Corollary 1, we have that $\Delta_{2}^{2}(n)=|\mathcal{K}|$ where $\mathcal{K}$ is a connected homogeneous simplicial $2$-complex. By the necessity of homogeneity, $\partial \mathcal{K}$ is a closed polygon (is it necessarily convex?) with at most $n$-vertices. Let the degree of a vertex in $\mathcal{K}$ denote the number of adjacent vertices in $\mathcal{K}$. Then, let $b$ and $b_{d}$ denote the total number of vertices of $\partial \mathcal{K}$, and the number of those vertices that have degree $d$ in $\mathcal{K}$, respectively. Then, $b = b_{2} + b_{3} + b_{4} + b_{5}$. [From here, I don't know where to go, I want to employ Euler's polyhedron formula somehow. If $\partial \mathcal{K}$ is convex, could I say $\Delta_{2}^{2} = 2 - n + E(n)$, where $E(n)$ is a function which determines the number of edges of $\mathcal{K}$? Any ideas for how to determine E(n)?]

I appreciate any suggestions!

-
In the plane any three noncolinear points determine a triangle (equiv. a 2-simplex), so presumably you are asking about the maximum number of simplices with disjoint interior. I believe this is an easy application of Euler's formula. – hardmath May 6 '12 at 3:40
@hardmath, I think Samuel wants all the triangles to be congruent and equilateral (although I must say this isn't entirely clear). – Gerry Myerson May 6 '12 at 3:43
@GerryMyerson: Yes, I intended the triangles to all be congruent and equilateral, I apologize for the confusion. Is this just an easy application of Euler's polyhedral formula still? – Samuel Reid May 6 '12 at 4:43
@GerryMyerson: Thanks, I'm still wondering if the equilateral triangles are allowed to overlap. The mention of packings suggests this would not be allowed. Of course it is known that a lattice packing of equilateral triangles is optimal in the plane, but perhaps there's something more subtle to the Question. – hardmath May 6 '12 at 14:16
@hardmath: The simplexes are not allowed to overlap, think of it like this. What is the maximum number of simplexes possible given a connected homogeneous simplicial complex formed from n-vertices? – Samuel Reid May 6 '12 at 22:44

As it is given the vertices and equilateral triangles are connected "edge to edge" in the plane, Euler's formula for "faces" of planar graphs applies whether or not the simplicial complex is convex. Note that the count of faces includes one unbounded region in the plane, so:

$$n - 1 = e - s$$

where $n$ is the number of vertices, $e$ the number of (unit) edges, and $s$ the number of (unit) equilateral triangles (simplices). Let $f(n)$ denote the maximum possible $s$ for given $n$.

The vertices may be counted by degree, as you started to do:

$$n = b_2 + b_3 + b_4 + b_5 + b_6$$

where $b_i$ counts the vertices of degree $i$. Then, since every edge is between two vertices, $e = (2b_2 + 3b_3 + 4b_4 + 5b_5 + 6b_6)/2$.

Consider the special case that $n$ is a centered hexagonal number, say $3m^2 + 3m + 1$, with the vertices are arranged accordingly. Then number of simplices (unit equilateral triangles) packed in that way is $6m^2$. The vertices include $b_3 = 6$, $b_4 = 6(m-1)$, and $b_6 = 3m^2 - 3m + 1$, and the number of edges may computed accordingly as $9m^2 + 3m$.

These arrangements show that the ratio $f(n)/n$ tends in the limit to $2$. Note that $f(n)$ is strictly increasing for $n \ge 2$, because where an exterior edge exists, adding a vertex can add at least one simplex. I conjecture that $f(n+1) - f(n)$ is always one or two, and that optimal arrangements can be built from the centered hexagonal "building blocks".

-
It seems curious, but there's a paper published just last year about Isoperimetrically Optimal Polygons in the Triangular Grid. In particularly authors Nagy and Barczi prove that the hexagon has the least perimeter for a given area as well as the maximum area for a given perimeter. I was going to sketch a proof of this, but it seems this is a fairly active research topic. – hardmath May 9 '12 at 13:35
Thank you for the suggestions! I ended coming up with an answer of $\Delta_{2}^{2}(n) = 1 - n + \Delta_{2}^{1}(n)$ in terms of my terminology. I appreciate the answer and the reference to the paper by Nagy and Barczi. – Samuel Reid May 9 '12 at 17:09