Optimal point sets determining a single triangle 

Get Complete Project Material File(s) Now! »

Chapter 4 Proof of Theorem 1.2.2: Optimal point sets determining two triangles in R³

Additional De nitions and Lemmas:

We give the following additional de nitions and lemmas in order to streamline to proof of Theorem 1.2.2.
De nition 4.1.1. We denote a triangle with edge lengths e₁; e₂, and e₃ by   {e₁; e₂; e₃}.
Lemma 4.1.2. A collection of points lying on the surface of a sphere in R³ determining only two distinct triangles and two distinct distances, one of which is the radius of the sphere can have at most 4 points.
De nition 4.1.3. Let t₁ and t₂ be triangles. We say that t₁ and t₂ associate in a if either the two triangles share an edge length in common, or if there is a nite sequence of allowable triangles, T₀; : : : ; T_k, which are such that t₁ = T₀, t₂ = T_k, and for every pair of triangles, (T_i−1; T_i) with 1 ≤ i ≤ k, share an edge length in common. Further, we call the sequence T₀; : : : ; T_k an associating sequence of triangles.
Lemma 4.1.4. Suppose that S is a collection of n points determining t distinct triangles. Then the triangles are such that given any 2, an associating sequence of triangles may be constructed such that all of the triangles in the sequence are congruent to some of the t triangles determined by S.
Lemma 4.1.5. Suppose that S is a collection of n points determining t distinct triangles.
Then the number of distinct distances is at most 2t + 1.

Proof of Theorem 1.2.2

We next prove Theorem 1.2.2. The structure of this proof is to consider all possible con gurations of 7 points in R³, and to show that all such con guartions must determine at least 3 distinct triangles. This shows that F₃(2) ≤ 6. To show equality, we present a 6 point set which determines only 2 distinct triangles, vis. the vertices of the 3-orthoplex, or regular octahedron.

Proof of Theorem 1.2.2

Proof. Suppose that S is a 7 point set in R³ which determines exactly t = 2 distinct triangles, call these t₁ and t₂.
Since t₁ and t₂ must associate, and they are the only allowable triangles, they must share a common edge length. This is because no sequence of other allowable triangles may lie between t₁ and t₂ in an associating sequence, which pairwise share edges since there are no further allowable triangles.
By Lemma 4.1.5 we know that S determines at most 2t + 1 = 2(2) + 1 = 5 distinct distances. Hence, we can divide the proof into cases based upon the number of distinct distances determined by S.
Case 1: Suppose that S determines 5 distinct distances. Denote these by d₁; d₂; d₃; d₄, and d₅.
Since there are only two distinct triangles, by assumption, it follows that for all 5 distinct distances to appear, both of these triangles must be scalene, having but a single edge length in common.
Fix one point in S, call it O, and note that there are 6 distances from O to each of the other points in S. Since there can be at most 5 distinct distances present, it follows that 2 of these other points are of the same distance from O. Denote these points by and B, and WLOG, suppose the distance is d₁. Then we have that, OA = OB = d₁. Note that the triangle OAB is isosceles (and equilateral if AB = d₁), and is therefore non-congruent to either of the scalene triangles, which which implies that S determines a third distinct triangle, a contradiction.
Case 2: Suppose that S determines 4 distinct distances. Denote these by d₁; d₂; d₃, and d₄. Note that neither of the two triangles determined by S can be equilateral, and at most one can be isosceles. This will be argued by contradiction.
Proof of Note: Suppose one of the triangles determined by S, t₁, is equilateral. The second triangle, t₂, must associate with t₁, and since there are no other allowable triangles in S, t₂ must share at least one edge in common with t₁. This leaves at most 2 edges (of t₂) with edge lengths not yet assigned, but by assumption, there are 3 remaining distinct distances that must be present. Thus, Neither triangle may be equilateral.
Now suppose that both t₁ and t₂ are isosceles. This means that each of the 2 triangles determined by S contribute 2 distinct edge lengths for a maximum total of 4 distinct edge lengths. Since there must be, by assumption, 4 distinct distances determined by S, it follows that this maximum is achieved. However, this implies that no edges are shared between t₁ and t₂, and since there are no other allowable triangles in S, this implies that t₁ and t₂ do not associate. Hence, at most one of the two triangles is isosceles. This concludes the proof of the note.
As in the previous case, x one point in S, call it O, and note that there are 6 distances from this point to the other 6 points in S, which can be labeled by {A; B; C; D; E; F }. Since there are 4 distinct distances in S, at least 2 of the those 6 points must be equidistant from O. WLOG, suppose it is A and B, and label this distance by d₁.
Consider the remaining 4 distances from O to {C; D; E; F }. Suppose rst that one of these is d₁, say OC. Then, since the triangles OAB, OCB, and OAC all have two edges of length d₁, it follows from the note above that these must all be congruent triangles, since there can be at most one isosceles triangle, and hence AB = BC = AC. But this implies that ABC is equilateral, a contradiction of the note. Hence, none of the 4 distances from O to {C; D; E; F } is d₁.
But since there are 4 such distances and only 3 allowable distances, it follows that two of these must be the same, WLOG, suppose OC = OD = d₂. However, this implies that OAB and OCD are non-congruent isosceles triangles, a contradiction of the note proven above.
Since every case leads to a contradiction, it follows that S cannot determine 4 distinct distances.
Case 3: Suppose that S determines 3 distinct distances. Denote these by d₁; d₂, and d₃. Up to a relabeling of the distances, there are 5 possible pairs of triangles in this case. These pairs are given in Table 4.1.
We shall proceed by showing that each of these pairs of triangles lead to a contradiction.
Pair #1: Consider when {t₁; t₂} are as in Pair # 1 in Table 4.1.
Consider 3 points in S, call these A; B; and C, which are such that ABC ≅ t₁. WLOG, suppose that AB = d₁, AC = d₂, and BC = d₃. This triplet of points exist since S determines t₁. Let D ∈ S, be distinct from the points {A; B; C}. Since S determines only the triangles t₁ and t₂ and BC = d₃, it follows that BCD ≅ t₁.
Clearly, CD ≠ d₃.
If CD = d₂, then we note that the triangle    ACD has two edges of length d₂, vis. AC and CD, which is a contradiction, since this would imply that S determines a third distinct triangle.
If, on the other hand, CD = d₁, then we note that Given another distinct point, E ∈ S, CE = d₁, since else we could relabel E by D and proceed as before. However, this means that the triangle BDE has two edges of length d₂, a contradiction since this would imply, as before, that S determines a third distinct triangle.
Pair # 2: Consider when {t₁; t₂} are as in Pair # 1 in Table 4.1.
Here note that the argument from Pair # 1 relied solely on t₁ being scalene, and showed that in such cases at least 2 distinct isosceles triangles can be constructed, implying that S, determines at least 3 distinct triangles. Since t₁ here is scalene, the argument from Pair # 1 applies precisely in this case as well, meaning that Pair # 2 is also not possible.
Pair # 3: Since both t₁ and t₂ are determined by S, we know that both must appear, and since the shared edge length appears once on the rst tirangle, and twice on the second, there exist 4 points in S, call them A; B; C; and D, such that ABC ≅ t₁, BCD ≅ t₂, and CD = d₃. However, then the triangle ACD has an edge of length d₁ and an edge of length d₃, which implies that S determines a third distinct triangle, a contradiction. Hence, Pair #3 is not possible.
Pair # 4: Since both t₁ and t₂ are determined by S, we know that both must appear, and since they share only a single edge in common, vis. the edge of length d₂, it follows that there must four points in S, call them A; B; C; and D, such that BC = d₂, ABC ≅ t₁, and BCD ≅ t₂. But then ABD has one edge of length d₁ and another of length d₃, which means that is is congruent to neither t₁ nor t₂, but this imples that S determines a third distinct triangle, a contradiction. Hence, Pair # 4 is not possible.
Pair # 5: Since both t₁ and t₂ are determined by S, we know that both must appear and share an edge of length d₁. If they lie such that the unique edge of each triangle (note both t₁ and t₂ are isosceles and so have a unique edge and a repeated edge) share a vertex, then the triangle formed by this shared vertex point and the points at the other ends of these edges has an edge of length d₂ (the unique edge of t₁) and an edge of length d₃ (the unique edge of t₂), meaning it is congruent to neither t₁ nor t₂, a contradiction. Hence, Pair #5 is not possible.
Since every possible pair of triangles determining exactly 3 distinct distances results in S determining a third distinct triangle, it follows that S cannot determine 3 distinct distances.
Case 4: Suppose that S determines only 2 distinct distances. Denote these by d₁ and d₂. Suppose that there exists a point in S, call it O, which is such that at least 5 of the other points in S are at a distance d₁. Then these 5 points lie on the surface of a sphere of radius d₁, and determine exactly one other distances (vis. d₂). This is not possible, by Lemma 4.1.2. Hence, it follows that for any point in S, call itO, there are two points in S, A and B, such that OA = OB = d₁, and 2 other points in S, call them E and F , such that OE = OF = d₂. Hence, for any choice of O ∈ S, we get Figure 4.1.
We now note that with exactly 2 distinct triangles and 2 distinct distances, there are (up to relabeling) 3 possible pairs of triangles. These are given in Table 4.2. We shall proceed by showing that each of these pairs cannot occur.
Pair # 1 Suppose that OAB ≅ t₁. (Note that if this is not the case, then OEF ≅ t₁ and we may exchange the labels on d₁ and d₂ and the labels on A and B with those on E and F , yielding the assumed congruence.) Since OAB ≅ t₁ and OAB ≅~ OEF , it is clearly follows that OEF ≅ t₂. However, this implies that t₂ has two edges of length d₂, a contradiction. Hence, Pair # 1 cannot occur.
Pair # 2 Here we note that we can re ne the situation of Figure 4.1 by noting that AB = d₂ and EF = d₁. Suppose that OC = d₁. If this is not the case, then we exchange the labels of d₁ and d₂, as well as A and B with E and F .
Now note that OBC and OAC must be congruent to t₁ since the have 2 edges of length d₁. It follows then that AC = BC = d₂. But this implies that ABC is an equilateral triangle with edge length d₂, a contradiction. So Pair # 2 cannot occur.
Pair # 3 Here we re ne the situation of Figure 4.1 by noting that AB = EF = d₁.
If OC = OD = d₁ then we note that {O; A; B; C; D } are all related by a single distance and so would imply that the 3-simplex could contain 5 points, a con-tradiction. Hence, WLOG, OD = d₂. If OC = d₂ as well, then we note that the points v = {C; D; E; F } are related by a single distance, vis. d₁, and so form the vertex set of a 3-simplex. Next note that each of the points O, A, and B relate to the points in v solely by the distance d₂. Hence, each of these 3 points is equidistant from the points in v, but there can be only one such point, namely the circumcenter of the points in v. Hence, it must be that OC = d₁. But now the previous argument holds with v = {O; A; B; C}. Thus, Pair # 3 cannot occur either.
Since all possible pairs of triangles determining exactly 2 distinct distances results in a contradiction, it follows that S cannot determine 2 distinct distances. Further, since every possible number of distinct distances determined by S results in a contradict, S a 7 point set determining exactly 2 distinct triangles cannot exist in R³. Hence, F₃(2) ≤ 6.

Contents
1 Introduction 
1.1 Historical Background:
1.2 Main Results:
2 Observations & Conjectures: 3
2.1 Observations in Connection with Theorem 1.2.1:
2.2 Conjecture Regarding Higher Dimensions:
2.3 Conjecture Regarding Three Distinct Triangles:
3 Proof of Theorem 1.2.1: Optimal point sets determining a single triangle 
3.1 Denitions and Lemmas
3.2 Proof of Theorem 1.2.1
4 Proof of Theorem 1.2.2: Optimal point sets determining two triangles in R3 
4.1 Additional Denitions and Lemmas:
4.2 Proof of Theorem 1.2.2
5 Proofs of Lemmas: 
5.1 Denitions Needed for the Proofs of Lemmas
5.2 Proof of Lemma 3.1.5
5.3 Proof of Lemma 4.1.2
5.4 Proof of Lemma 4.1.4
5.5 Proof of Lemma 4.1.5
GET THE COMPLETE PROJECT
Optimal Point Sets with Few Distinct Triangles