.PH ""
.EQ
delim $$
.EN
.nr Pt 1
.nr Eq 1
.nr Au 0
.am DE
.sp
.ls 2
..
.ce 99
.B
Partitions of planar sets into small triangles
.R
.sp
by
.sp
.I
Andrew M. Odlyzko
.R
AT&T Bell Laboratories
Murray Hill, NJ 07974
.sp
.I
Ja\*'nos Pintz
.R
Mathematical Institute
Hungarian Academy of Sciences
H-1053 Budapest
Re\*'altanoda u. 13-15 Hungary
.sp
and
.sp
.I
Kenneth B. Stolarsky
.R
Department of Mathematics
1409 West Green Street
University of Illinois
Urbana, Illinois 61801
.sp 1.5
.I
ABSTRACT
.R
.ce 0
.sp
.P
Given $3n$ points in the unit square, $n~>=~2$, they
determine $n$ triangles whose vertices exhaust the given
$3n$ points in many ways.
Choose the $n$ triangles so that the sum of their areas
is minimal, and let $a * (n)$ be the maximum value of
this minimum over all configurations of $3n$ points.
Then $n sup -1/2~<<~ a * (n)~<<~n sup -1/9$ is deduced
using results on the Heilbronn triangle problem.
If the triangles are required to be
.ul
area disjoint
it is not even clear that
the sum of their areas tends to zero;
this open question
is examined in a slightly more general setting.
.rs
.sp 3i
1980
.ul
Mathematics Subject Classification:
Primary 52A37, 52A40.
Secondary 52A45.
.sp 2
.ul
Key Words and Phrases:
Convex body, convex hull, disjoint triangulation,
Heilbronn's problem, triangulation.
.bp
.ce 99
.B
Partitions of planar sets into small triangles
.R
.sp
by
.sp
.I
Andrew M. Odlyzko
.R
AT&T Bell Laboratories
Murray Hill, NJ 07974
.sp
.I
Ja\*'nos Pintz
.R
Mathematical Institute
Hungarian Academy of Sciences
H-1053 Budapest
Re\*'altanoda u. 13-15 Hungary
.sp
and
.sp
.I
Kenneth B. Stolarsky
.R
Department of Mathematics
1409 West Green Street
University of Illinois
Urbana, Illinois 61801
.ce 0
.sp 2
.H 1 Introduction
.ls 2
Given a set $P~=~"{" p sub 1 , "..." , p sub 3n "}"$ of $3n$
points in a convex planar body $SIGMA$, let $a(n,P, SIGMA )$
denote the smallest sum of areas of a collection
$DELTA~=~"{" delta sub 1 , "..." , delta sub n "}"$ of $n$
triangles such that (i) the vertices of the $delta sub i$
exhaust the $3n$ points of $p$, and (ii) the intersection of
any $delta sub i$ with any $delta sub j$, $j~!=~i$, has
zero area.
A system of triangles satisfying (i) and (ii) shall henceforth
be called a
.ul
disjoint triangle partition.
.PH "''- \\\\nP -''"
.nr P 1
.P
Let $a(n, SIGMA )$ denote the supremum of $a ( n , P, SIGMA )$
over all sets $P~\(ib~SIGMA$ of $3n$ points, and let $a(n)$
denote the supremum of $a(n, SIGMA ) / A ( SIGMA )$ over all convex
planar sets $SIGMA$ of positive area.
We establish for $n~>=~2$ that
.DS 2
.EQ (1.1)
n sup -1/2 ~<<~
a(n)~<=~
0.8 ~+~ O( n sup -1 ) ~<=~0.9~.
.EN
.DE
Elementary considerations (see \(sc5) show that
the limit of $a(n)$ as $n~->~inf$ exists, but
the authors do not know whether or not it is
zero, although they can improve on (1.1) to some extent.
.P
If the disjointness requirement (ii) is dropped,
so that we ask for that collection of triangles
$DELTA~=~"{" delta sub 1, "..." , delta sub n "}"$
whose vertices exhaust the points of $P$ and
which has minimal sum of areas of the triangles,
the problem becomes somewhat more tractable.
Denote the function in this case by $a*(n)$,
so that $a(n)~>=~a*(n)$.
We show that for every $epsilon~>~0$,
.DS 2
.EQ (1.2)
n sup {- 1/2} ~<<~
a*(n)~<<~n sup {-1/8 + epsilon}~.
.EN
.DE
As is explained in Section\ 3, it seems likely that the lower
bound in (1.2) is close to the true value of $a sup * (n)$.
.P
Our problem is related to Heilbronn's
triangle problem, which asks for an
estimate of the area of the smallest
triangle determined by any three out
of $n$ points located in the unit square.
As a result of the deep work of
Schmidt [11], Roth [6-10], and Komlo\*'s,
Pintz, and Szemere\*'di [5] it is known [5]
that there is always a triangle of area
.DS 2
.EQ (1.3)
<<~~n sup {-8/7 + epsilon}~,
.EN
.DE
for every $epsilon~>~0$.
On the other side, Erdo\*:s' early example
[6] of a configuration without a triangle
of area $<<~n sup -2$ was recently improved
by Komlo\*'s, Pintz, and Szemere\*'di [4], who
showed that there are configurations without
triangles of area $<<~n sup -2 log~n$.
Our proofs rely on a modification of the
Erdo\*:s construction and on the Komlo\*'s,
Pintz, and Szemere\*'di result (1.3).
.H 1 "The Upper Bound"
We first establish that
.DS 2
.EQ (2.1)
a(2,P, LAMBDA )~<=~.8A( LAMBDA )
.EN
.DE
where $LAMBDA$ is the convex hull of the given
set $P$ of $3n~=~6$ points.
The argument splits into cases according to whether
.DS 2
.EQ (2.2)
b~=~| P \(ca partial LAMBDA |~,
.EN
.DE
the number of points of $P$ on the boundary $partial LAMBDA$
of the convex hull $LAMBDA$, is six, five, or at most four.
.P
Whenever there are two collections of triangles
$"{" delta sub 1 , "..." , delta sub n "}"$
and $"{" gamma sub 1 , "..." , gamma sub n "}"$
satisfying (i) and (ii) such that each $delta sub i$
is area-disjoint from each $gamma sub j$, clearly
one of the collections has total area at most
.DS 2
.EQ (2.3)
1 over 2~A( LAMBDA )~,
.EN
.DE
where $LAMBDA$ is the convex hull of $P$.
For $3n~=~6$ and $b~<=~4$, it is easy to
verify that two such collections exist.
.P
For $b~=~6$ label the vertices in clockwise order as
.DS 2
.EQ
"{" p sub 1 , "..." , p sub 6 "}"~=~ "{" B,C,D,E,F,G "}"~.
.EN
.DE
Then the three disjoint triangle partitions
.DS 2
.EQ (2.4)
"{" BCD,EFG "}",~~~"{" CDE , FGB "}" ,~~
"{" DEF , GBC "}"
.EN
.DE
have total combined area at most $2A ( LAMBDA )$,
so some one of them has total area at most
.DS 2
.EQ (2.5)
(2/3) A ( LAMBDA )~.
.EN
.DE
.P
Finally, suppose that $b~=~5$ and
.DS 2
.EQ (2.6)
"{" p sub 1 , "..." , p sub 5 "}"~=~
"{" B,C,D,E,F "}"
.EN
.DE
are the vertices,
in clockwise order, of a convex pentagon, inside of
which is $p sub 6~=~G$.
Then the hull $LAMBDA$ splits into five triangles
.DS 2
.EQ (2.7)
GBC,~GCD,~GDE,~GEF,~GFB~,
.EN
.DE
so without loss of generality
.DS 2
.EQ (2.8)
A(GDE)~>=~1 over 5~A( LAMBDA )~.
.EN
.DE
Now $G$ lies in one of the triangles
.DS 2
.EQ (2.9)
BFE ,~BED ,~BDC ~;
.EN
.DE
without loss of generality it lies in $BFE$ or $BED$.
Thus
.DS 2
.EQ (2.10)
"{" BCD , GEF "}"
.EN
.DE
forms a disjoint triangulation of area at most
.DS 2
.EQ (2.11)
A ( LAMBDA )~-~
A ( GDE )~<=~ .8A ( LAMBDA )
.EN
.DE
by (2.8).
This proves (2.1).
.P
We now establish the right inequality of (1.1).
Let $m$ be a positive integer.
To find a disjoint triangulation for $P~\(ib~SIGMA$
where $| P |~=~6m+3$, start with a vertical line $t$
outside and to the left of $SIGMA$.
We may assume (rotate $SIGMA$ if necessary) that
none of the $<=~( pile {3n above 2} )$ lines
determined by the $3n$ points is parallel to $t$.
Then find $M~=~2m+2$ lines $t sub 1 , "..." , t sub n$
parallel to $t$, each to the right of the previous one,
such that (a) in each closed strip $T sub i$
formed by $t sub i$, $t sub i+1$ there are 3
distinct elements of $P$, namely $p sub i1$,
$p sub i2$, $p sub i3$, and (b) the union of
all $"{" p sub i1 , p sub i2 , p sub i3 "}"$ is $P$.
(Remarks: (1) Some of the $t sub i$ may coincide
due to multiple points.
(2) If $SIGMA$ is a rectangle with two sides parallel
to $t$, the triangles
$p sub i1$, $p sub i2$, $p sub i3$ immediately provide
a disjoint triangulation of area at most $.5A ( LAMBDA )$.)
.P
The procedure now is to combine pairs of adjacent strips
to produce roughly half the original number of parallel
strips, with each new strip containing 6 distinct points
of $P$.
Of course, there will be one strip $T*$ left over that
contains only 3 points.
Since there are $m+1$ ways of doing this, we can insure
that $T*$ intersects $SIGMA$ in a set of area at most
.DS 2
.EQ (2.12)
A ( SIGMA ) / (m+1)~,
.EN
.DE
and hence the triangle formed by the points in $T*$
has at most this much area.
.P
The first result of this section shows that the six
points in each of the remaining $m$ strips $T sub i$
can be triangulated so that at most .8 of each
$T sub i~\(ca~SIGMA$ is covered.
Let $alpha$ be the fraction of the area of $SIGMA$
that lies in $T*$.
Then the fraction of $SIGMA$ covered by the resulting
disjoint triangulation is at most
.DS 2
.EQ (2.13)
\&.8 (1- alpha ) ~+~
alpha ~<=~.8 ~+~ .2 over m+1~<=~.9~.
.EN
.DE
If $| P |~=~6m$ the argument simplifies, and we have
the better upper bound .8.
This proves the right inequality of (1.1).
.H 1 "No Disjointness Requirement"
We now use the Komlo\*'s, Pintz, and Szemere\*'di result
(1.3) to prove the upper bound of (1.2).
We first prove a general result which gives an upper bound
for $a sup * (n)$ in terms of any upper bound for Heilbronn's
triangle problem.
Since the asymptotic behavior of $a sup * (n, sum ) /A ( sum )$ is
the same for all convex $sum$, we will take $sum$ to be the unit square.
.sp
\f2Notation\f1:\0\0Let $DELTA (n)$ denote the maximum possible
value of the minimum of the areas of the triangles $p sub i p sub j p sub k$
(taken over all selections of three out of $n$ points $p sub 1 ^,...,^ p sub n$),
where the maximum is taken over all distributions of
$p sub 1 ^,...,^ p sub n$ in the unit square.
Let $DELTA tilde (n) ~=~ DELTA (3n)$.
.sp
\f2Theorem\f1.
.I
If $1 <= f(n) <= n sup lambda$ is monotonically increasing and
.R
.DS 3
.EQ (3.1)
DELTA tilde (n) ~<=~ f(n) over {n sup {1+ lambda}} ^,
.EN
.DE
.I
where $0 < lambda <= 1$, then
.R
.DS 3
.EQ (3.2)
a sup * (n) ~<=~ 500 over lambda (f(n) n sup {- lambda} ) sup {1 over {1+
lambda}} ~.
.EN
.DE
\f2Proof\f1.
The upper bound $a sup * (n) ~<=~ 1$ implies the claimed assertion
for $n ~<=~ 24$, for example.
We suppose that the assertion is true for all $j < n$, where
$n >= 25$.
We divide the square into 4 smaller squares of area 1/4 and choose
one of these little squares, say $Q prime$, which contains at least
$3n/4$ points.
By possibly shrinking $Q prime$ to a square $Q {prime prime}$ we can
assume that the number of points in $Q {prime prime}$ is $3k$ with
$n-3 over 4 ~<=~ [n/4] <= k <= n-1$ (if we additionally make the
convention that points on the boundary of $Q {prime prime}$ are to be
considered (separately) to belong to $Q {prime prime}$ or not
according to our decision).
Now we proceed as follows.
.br
1) We choose the smallest triangle in $Q-Q {prime prime}$, afterwards
the smallest remaining triangle in $Q-Q {prime prime}$, etc., until
the number of remaining points is $3[M]$, where
.DS 3
.EQ
M ~=~ {(f(n) ^cdot^ n) sup {1 over {1+ lambda}}} over 100 ~.
.EN
.DE
(Note $M <= n/100$.)
The sum of the areas of these triangles is
.DS 3
.EQ
<= ~ sum from {scrL =[M]+1} to n-k ~mark DELTA tilde ( scrL ) ~<=~ f(n)
sum from {scrL =[M]+1} to inf ~1 over {scrL sup {1+ lambda}} ~<=~ {2f(n)} over
{lambda M sup lambda}
.EN
.sp
.EQ (3.3)
~lineup <= ~200 over lambda (f(n) n sup {- lambda} ) sup {1 over {1+ lambda}}~.
.EN
.DE
2) To each of the $3[M]$ remaining points in $Q-Q {prime prime}$
we associate successively 2 points from $Q {prime prime}$ so that
the resulting $3[M]$ triangles (with disjoint vertices) all have areas
.DS 3
.EQ
<= ~ 1 over 2 ( sqrt 2 ) sup 2 sin {2 pi} over {3n over 4 - 6M} ~<=~ 10 over n
~.
.EN
.DE
The sum of the areas of these triangles is therefore
.DS 3
.EQ (3.4)
<= ~ 30M over n ~<~ (f(n) n sup {- lambda} ) sup {1 over {1+ lambda}} ~.
.EN
.DE
3) Finally for the remaining $3k-6[M]$ points in $Q {prime prime}$,
where
.DS 3
.EQ
n over 5 ~<=~ n-3 over 4 ~-~ n over 50 ~<=~ k-2 [M] ~<=~ n-1 ~,
.EN
.DE
we have by our inductive hypothesis $k-2 [M]$ triangles with
total area
.DS 3
.EQ
mark <=~ 1 over 4 ^ a sup * (k-2 [M]) ~<=~ 1 over 4 ~cdot~ 500 over lambda
(f(n) ~( n over 5 ) sup {- lambda} ) sup {1 over {1+ lambda}}
.EN
.sp
.EQ (3.5)
lineup <=~ 125 over lambda ~cdot~ sqrt 5 (f(n) n sup {- lambda} ) sup
{1 over {1+ lambda}} ~.
.EN
.DE
.P
Summing the areas of all these triangles ((3.3)-(3.5)) we obtain
.DS 3
.EQ
a sup * (n) ~<=~ 500 over lambda (f(n) n sup {- lambda} ) sup {1 over
{1+ lambda}} ~,
.EN
.DE
as claimed.
.sp
\f2Remark\f1.
Since we know by [5] that $DELTA (n) ~<<~ n sup -9/8$, for example,
we are entitled to suppose $lambda >= 1/8$ and so the constant
$500/ lambda$ can be replaced by 4000.
.P
Using the inequality
.DS 3
.EQ
DELTA (n) ~<<~ e sup {c {sqrt {log~n}}} ~cdot~ n sup -8/7
.EN
.DE
proved in [5], we obtain
.sp
\f2Corollary 1\f1.
$a sup * (n) ~<<~ e sup {c prime {sqrt {log~n}}} ~cdot~n sup -1/8$.
.P
Although Heilbronn's conjecture was disproved in [4] by showing that
.DS 3
.EQ
DELTA (n) ~>>~ n sup -2 ~ log ~n ~,
.EN
.DE
one may conjecture that $DELTA (n) ~<<~ n sup {-2 + epsilon}$, however.
.sp
\f2Corollary 2\f1.
The conjecture $DELTA (n) ~<<~ n sup {-2 + epsilon}$ implies that
$a sup * (n) ~<<~ n sup {-1/2+ epsilon}$.
.P
The strongest possible conjecture $DELTA (n) ~<<~ n sup -2 log ~n$
would imply $a sup * (n) ~<<~ n sup -1/2 ( log ~n) sup 1/2$.
.P
These results show that probably the inequality $a sup * (n) ~>>~ n sup -1/2$
cannot be improved significantly.
Our Theorem also shows that a proof of a relation of type
${lim bar} from {n -> inf} ~a sup * (n) n sup 1/2 ~=~ inf$
would imply ${lim bar} from {n -> inf} ~DELTA (n) n sup 2 ~=~ inf$,
so it would lead to a new disproof of Heilbronn's conjecture
(if the inequality $DELTA (n) ~>>~ n sup -2 log ~n$
is not used in course of the proof, naturally).
This connection shows that the following problem might be interesting.
.sp
\f2Problem\f1.
Is it true that $a sup * (n) ~<<~ n sup -1/2$?
.H 1 "The Lower Bound"
Since
.DS 2
.EQ (4.1)
a*(n)~<=~a(n)~,
.EN
.DE
the left side of (1.1) follows immediately
from the left side of (1.2), which we shall
establish after a preliminary lemma.
.sp
.I
Lemma.
Let $p$ be an odd prime, and let
$z sub 1 , "..." , z sub p$ be the
lattice points in
.DS 2
.EQ
[0, p-1]~times~
[0,p-1]
.EN
.DE
whose coordinates are congruent
modulo $p$ to those of
.DS 2
.EQ
(k,k sup 2 ) ,~~~0~<=~k~<=~p-1~.
.EN
.DE
Then (i) every triangle formed by 3 distinct
$z sub i$ has area at least 1/2 and (ii) we
have
.DS 2
.EQ (4.2)
sum from i<j~
1 over {| z sub i - z sub j |}~<=~8 sqrt 2 (p-1)~.
.EN
.DE
.sp
.I
Proof.
.R
Statement (i) is an observation of Erdo\*:s [6, Appendix];
simply note that the area is half the value of a
determinant that is not congruent to 0 modulo $p$.
.P
For (ii), first observe the general inequality
.DS 2
.EQ (4.3)
(a sup 2 + b sup 2 ) sup -1/2~<=~sqrt 2 /
(| a | + | b | )~.
.EN
.DE
Write $z sub i~=~( x sub i , y sub i )$ and let
$N(k)$ be the number of solutions of
.DS 2
.EQ (4.4)
| x sub i - x sub j | ~+~
| y sub i - y sub j |~=~k~,~~~
i~<~j~.
.EN
.DE
Clearly the sum on the left side of (4.2) is bounded by
.DS 2
.EQ (4.5)
sqrt 2~
sum from k=1 to 2p-2 ~N(k)/k~.
.EN
.DE
Now if
.DS 2
.EQ (4.6)
0~<=~a,b~<=~p-1~,
.EN
.DE
then the simultaneous equations
.DS 3
.EQ (4.7)
x sub i - x sub j~mark ==~
a~roman mod~p~,
.EN
.sp
.EQ
x sub i sup 2 - x sub j sup 2 ~lineup ==~
b ~roman mod~ p~,
.EN
.DE
have at most one solution with $i~<~j$ modulo $p$.
Hence $N(k)~<=~4k$ and the lemma follows.
$blot$
.P
To prove our claimed result, it suffices to
show that there is a way of placing $3n$
points inside the unit square so that the
area covered by any vertex-disjoint triangulation
is $>>~n sup -1/2$.
.P
In what follows, $P$ is a set of $approx~n$ points
with a distinguished subset $Q$ of $approx~sqrt n$
points.
The cardinality of $P$ shall be divisible by 3.
It clearly suffices to construct such a set $P$ in
an $s times s$ square $PHI$, where $s~approx~sqrt n$,
so that every triangle of $P$ with some vertex in $Q$
has area at least $1/2$ (the total area of these
triangles is $>>~sqrt n$, while the square has area $<<~n$).
.P
Let $p$ be an odd prime such that
.DS 2
.EQ
p~<~sqrt n~<=~2p~.
.EN
.DE
The square $PHI$ shall be
.DS 2
.EQ
[0,100 p ]~times ~[ 0,100  p ]~,
.EN
.DE
and the distinguished subset $Q$ shall be the set
$"{" z sub 1 , "..." , z sub p "}"$ of the lemma.
The set $P$ shall consist of $Q$ together with
.DS 2
.EQ
p sup 2 - p ~~~( roman or~~
p sup 2 - p+1 ~~roman or~~
p sup 2 - p+2 )
.EN
.DE
points on a certain vertical line segment $t$ such
that no two are closer than $1/p$.
For $t$ we choose the rightmost vertical edge of $PHI$; i.e.,
.DS 2
.EQ (4.8)
t~=~"{" (x,y) ~:~
x~=~100 p~,~~~0~<=~y~<=~100 p "}"~.
.EN
.DE
.P
If all 3 vertices of a triangle $delta$ lie in $Q$, then
$A( delta ) ~>=~1/2$ by the lemma.
If one vertex of $delta$ lies in $Q$, it has area
.DS 2
.EQ (4.9)
>=~1 over 2 ~ (100-1)p(1/p)~>=~1 over 2~.
.EN
.DE
.P
Finally, if 2 vertices of $delta$,
say $z sub 1$, $z sub 2$, lie in $Q$,
consider the line $scrL$ joining them.
If its slope exceeds 2 (say) in absolute value,
the area $delta$ of triangle $z sub 1 z sub 2 z sub 3$
for any $z sub 3$ on $t$ is clearly very large.
If the slope is less than 2 and $q$ is the intersection of $t$
and $scrL$, then
.DS 2
.EQ (4.10)
A( delta ) ~=~
A ( delta ( z sub 1 z sub 2 z sub 3 ) )
~>=~| z sub 1 - z sub 2 | h / ( 2 ( 1 sup 2 + 2 sup 2 ) sup half )~,
.EN
.DE
provided every point of $P$ on $t$ is at least
$h$ units of distance above or below $q$.
To insure that each such $A( delta )$ is at least $1/2$,
it suffices to exclude from $t$ a collection of
subintervals of total length no more than
.DS 2
.EQ (4.11)
sigma~=~2~
sum from i<j~
sqrt 5 over {| z sub i - z sub j |}~<=~16 sqrt 10~
p~<~64p~,
.EN
.DE
by the lemma.
Clearly enough remains of $t$ to carry out the
construction $(36p/(p sup 2 - p+2)~>~1/p)$, so the
result follows.
.H 1 "Existence of a Limit, and Epsilon Simplicity"
For any integer $q$ we have
.DS 2
.EQ (5.1)
3n~=~3qm + 3r ~,~~~0~<=~r~<~q~.
.EN
.DE
Let
.DS 2
.EQ (5.2)
f(n)~=~a ( n,P, SIGMA ) / A ( SIGMA )~.
.EN
.DE
The argument at the end of \(sc2 shows that
.DS 3
.EQ (5.3)
f(n)~mark <=~f(q)(1- alpha ) + alpha
.EN
.sp
.EQ
lineup <=~
f(q)+ (1-f(q))/(m+1)~<=~f(q)~+~1 over m+1~,
.EN
.DE
where, by (5.1), we have
.DS 2
.EQ (5.4)
m~=~[n/q]~.
.EN
.DE
Hence
.DS 2
.EQ (5.5)
{lim ~roman "sup"} from {n -> inf}~
f(n)~<=~f(q)~,
.EN
.DE
and it follows immediately from (5.2)
that $a(n, SIGMA )$ has a limit as $n~->~inf$.
.P
We can make another use of (5.3).
A statement that can be put in the form
.DS 2
.EQ (5.6)
x~=~0
.EN
.DE
shall be called
.ul
epsilon-simple
if knowledge of its truth (provided, say,
by an oracle) enables us to
.ul
explicitly write down
a proof of
.DS 2
.EQ (5.7)
| x | ~<~epsilon
.EN
.DE
for any given rational $epsilon~>~0$ (the proof
may be different for different values of $epsilon$).
For example, a well-known though unpublished paper
of J. B. Rosser establishes the epsilon-simplicity
of the prime number theorem by means of the old
Chebyshev method (see [2, pp. 578-581]).
.P
Say $SIGMA$ is the unit square.
We show that the statement
.DS 2
.EQ (5.8)
lim from {n -> inf}~
a ( n, SIGMA )~=~0~,
.EN
.DE
if true, is epsilon simple.
By the continuity of the area
of a triangle as a function of
its vertices, we can compute $a( q, SIGMA )$,
for any fixed constant value of $q$, to within
any preassigned tolerance $eta$.
(Simply examine all sets of $q$ triangles whose
vertices lie on a rational grid with mesh size
very small compared to $eta$).
Since $m ~->~inf$, as $n~->~inf$, the result
follows from (5.3).
Of course, given an $epsilon$, this crude method
does not given us any
.ul
a priori
bound on the length of the proof as a function of $epsilon$.
.H 1 Remarks
What makes this problem seemingly harder than
Heilbronn's is the requirement of disjointness.
However, if $3n$ points are in Euclidean 3 space
(say $n$ are red, $n$ are white and $n$ are blue)
and no 4 are coplanar, then there is a disjoint
triangulation into tricolored triangles.
This was shown nicely by means of the "Ham Sandwich Theorem"
independently by Karl W. Heuer, Richard Goldstein, and D. Winter [3].
.bp
.ce
.B
REFERENCES
.R
.RL
.LI
C. E. Corzatt, Some extremal problems of number theory
and geometry, Doctoral Dissertation, University of Illinois,
Urbana, 1976 (unpublished).
.LI
H. G. Diamond, Elementary methods in the study of the distribution
of prime numbers, Bull. Amer. Math. Soc. (New Series) 7(1982), 553-589.
.LI
R. Goldstein, K. W. Heuer, and D. Winter, Partition of $S$ into
$n$ triples, Solution to Problem 6316, Amer. Math. Monthly
89(1982), 705-706.
.LI
J. Komlo\*'s, J. Pintz, and E. Szemere\*'di, A lower bound
for Heilbronn's problem, J. London Math. Soc. (2) \f325\f1
(1982), 13-24.
.LI
J. Komlo\*'s, J. Pintz, and E. Szemere\*'di, On
Heilbronn's triangle problem,
J. London Math. Soc. (2) \f324\f1 (1981), 385-396.
.LI
K. F. Roth, On a problem of Heilbronn, J. London Math. Soc.
26(1951), 198-204.
.LI
K. F. Roth, On a problem of Heilbronn II, Proc. London Math.
Soc. (3) 25(1972), 193-212.
.LI
K. F. Roth, On a problem of Heilbronn III, Proc. London Math.
Soc. (3) 25(1972), 543-549.
.LI
K. F. Roth, Estimation of the area of the smallest
triangle obtained by selecting three out of $n$
points in a disc of unit area, pp. 251-262 in
.ul
Analytic Number Theory,
H. Diamond, ed., Proc. Symp. Pure Math., Vol. 24,
Am. Math. Soc., 1973.
.LI
K. F. Roth, Developments in Heilbronn's triangle problem,
Advances in Math. \f322\f1 (1976), 364-385.
.LI
W. M. Schmidt, On a problem of Heilbronn, J. London Math.
Soc. (2) 4(1971/2), 545-550.
.LE