2
$\begingroup$

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!

  • 0
    Dumi$t$rescu, Pach, and Toth, The maximum number of empty congruent triangles determined by a point set, might be of interest, at http://www.math.nyu.edu/~pach/publications/triangles050605.pdf2012-05-07

1 Answers 1

1

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".

  • 0
    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.2012-05-09