Abstract. The problem considered in [4] and [3] is as follows: Given n
red points and m green points on plane, how to find a pair of red-green
points such that the distance between them is smallest. This problem can
be expanded for 3 sets of colored points [5]: Given n red points, m green
points and p blue points on plane, how to find a trio of red-green-blue points
such that the diameter of them is smallest. The diameter of the trio of 3-
colored points is defined as size of the longest edge of the triangle formed
by those 3 points. This problem seems to be a fundamental problem, but it
is still open. An heuristic algorithm for this problem can be found in [5].
For the case that the sets of the given points are infinity, for example, the
set of points on a line, then the combinatorial algorithm does not work any
more. In this paper we will use geometric methods to solve the following
problem: Given a triangle ABC, how to find a trio of points M, N and P
lying on the side BC, CA and AB, respectively, such that the diameter of
the triangle MNP is smallest.

6 trang |

Chia sẻ: thanhle95 | Lượt xem: 170 | Lượt tải: 0
Bạn đang xem nội dung tài liệu **Inscribed triangle with smallest diameter**, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

JOURNAL OF SCIENCE OF HNUE
2011, Vol. 56, N◦. 1, pp. 34-39
INSCRIBED TRIANGLE WITH SMALLEST DIAMETER
Vu Dinh Hoa
Hanoi National University of Education
E-mail: hoavd@hnue.edu.vn
Abstract. The problem considered in [4] and [3] is as follows: Given n
red points and m green points on plane, how to find a pair of red-green
points such that the distance between them is smallest. This problem can
be expanded for 3 sets of colored points [5]: Given n red points, m green
points and p blue points on plane, how to find a trio of red-green-blue points
such that the diameter of them is smallest. The diameter of the trio of 3-
colored points is defined as size of the longest edge of the triangle formed
by those 3 points. This problem seems to be a fundamental problem, but it
is still open. An heuristic algorithm for this problem can be found in [5].
For the case that the sets of the given points are infinity, for example, the
set of points on a line, then the combinatorial algorithm does not work any
more. In this paper we will use geometric methods to solve the following
problem: Given a triangle ABC, how to find a trio of points M , N and P
lying on the side BC, CA and AB, respectively, such that the diameter of
the triangle MNP is smallest.
Keywords: The diameter, trio of 3-colored points, triangles
1. Introduction
The problem of 3-colored points on plane is among the series of min-max
problems, see [1, 2, 3, 4]. The problem could be described as follows: Given n red
points, m green points and p blue points on plane, how to find a trio of 3 different-
colored points such that the diameter of them is smallest. The diameter of the trio of
3-colored points is defined as size of the longest edge of the triangle formed by those
3 points. This problem can be solved by applying an exhaustive search algorithm:
testing every trio of 3 different colored points and finding the closest one. Totally,
there are n.m.p trios of 3-colored points and if we do an exhaustive search, it will
take n.m.p operations. The complexity of this algorithm, therefore, is O(nmp). An
heuristic algorithm is based on 2D Voronoi Diagram.
For the case that the sets of the given points are infinity, for example, the set of
points on a line, then the combinatorial algorithm does not work any more. In this
paper we use the geometric methods to solve the following similar problem: Given
34
Inscribed triangle with smallest diameter
a triangle ABC, how to find a trio of points M , N and P lying on the side BC, CA
and AB, respectively, such that the diameter of the triangle MNP is smallest.
Similar problems are already known in geometry. For example, the problem of
finding an inscribed triangle in a given triangle such that its perimeter is smallest,
or the problem of a cat finding a point so that its distance to the furthest one of the
three given exits of a mouse’s hole should be a minimum.
2. Results
Given a triangle ABC. We look for an inscribed triangleMNP withM ∈ BC,
N ∈ CA and P ∈ AB such that the diameter ofMNP is a minimum. Our problem
may be formed as an analysis problem and it is easy to see that such a trio of points
M , N and P with the smallest diameter always exists. But, we can describe it
geometrically.
We begin our proof with a trivial observation:
Lemma 2.1. Let P , N and M be points on the edges AB, AC and BC respectively
and H be the foot of perpendicular dropped of P on AC. Suppose that PN > NM .
If NH ∩ AC 6= {N} then there exists N ′ 6= N on AC such that PN ′ < PN and
N ′M < PN .
Note that NH ∩AC = {N} occurs only in one of the following cases in Figure
1.
P
H A = N
H
P
A
C = N
BCBB C
A
H = N
P
Figure 1. The case AC ∩HN = {N}
The two following lemmas are also well-known results.
Lemma 2.2. Let M , N and P be points on the edges BC, CA and AB of a triangle
ABC, then the circumscribed circles (ANP ), (BPM) and (CMN) are concurrent.
The easy proof for the next lemma is left to the reader.
Lemma 2.3. Two circles (O1) and (O2) in a plane intersect. Let P be one of the
points of intersection. Consider a segment AB going through P with A ∈ (O1) and
B ∈ (O2). The length of the segment AB is maximal if and only if the line AB is
parallel to the line O1O2.
35
Vu Dinh Hoa
Lemma 2.4. Suppose MNP is an inscribed triangle with the smallest diameter d,
then MNP is an isosceles triangle such that the length of its two edges is d and the
last edge has a length ≤ d.
Proof. We prove the Lemma by contradiction. Suppose the otherwise that NP >
NM and NP > MP . If AC ∩ NH 6= {N}, by Lemma 2.1, we have a point
N ′ ∈ AC such that PN ′ < PN and MN ′ < PN and therefore the triangle MN ′P
has a diameter less than d, a contradiction. If AC ∩ NH = {N} then one of the
cases in Figure 1 must occur and we can use similar argument as in Lemma 2.1 for
N instead of P to get a point P ′ ∈ AB such that P ′N < PN and P ′M < PN and
therefore the triangle MNP ′ has a diameter smaller than d. In both cases we get
a contradiction with the fact that d is the smallest diameter. Thus, if MNP is an
inscribed triangle with smallest diameter d, then MNP is an isosceles triangle with
two edges of length d and the third edge has a length be smaller than or equal to
d.
Theorem 2.1. Given triange ABC, then
a) If max{Â, B̂, Ĉ} ≥ 120◦, say Â ≥ 120◦, then the inscribed triangle with small-
est diameter is the triangle MNP , where AM is the bisector of angle Â and
N and P are the feet of the perpendicular dropped of M onto the edges AC
and AB respectively.
b) If 120◦ ≥ max{Â, B̂, Ĉ} then the inscribed triangle with the smallest diameter
is the inscribed equilateral triangle with the smalles edge.
Proof. a) Since Â ≥ 120◦ we have P̂MN ≤ 60◦, thus MP = MN ≥ PN . Now
let M ′N ′P ′ be an arbitrary inscribed triangle in triangle ABC (see Figure 2).
Without loss of generality suppose that M ′ ∈MC. Then M ′H ′ ≥MP where
H ′ is the foot of the perpendicular dropped fromM ′ onto the line AB. Clearly,
M ′P ′ ≥M ′H ′ ≥MP and thus the diameter of the triangle M ′N ′P ′ is greater
than the diameter of the triangle MNP .
M
A
B C
N
P
M ′
N ′
P ′
H ′
Figure 2. The case Â ≥ 120◦
b) Let MNP be the inscribed triangle with the smallest diameter d. By Lemma
2.4, MNP is an isosceles triangle, say MP = MN = d and NP ≤ d. We
36
Inscribed triangle with smallest diameter
will show that NP = d. Suppose the otherwise that NP < d. Let H1 and
H2 be the feet of perpendicular dropped from M onto the edges AC and AB
respectively. Note that the case H1 = N and H2 = P does not occur, since
NP < MP = MN = d and Â ≤ 120◦. Thus, we can suppose that H1 6= N
(the case H2 6= P is similar). By Lemma 2.1 using forMN and NP instead of
PN and NM , we have H1N∩AC = {N}, since by otherwise we can choose an
point N ′ such that PN ′ < NM and N ′M < NM and the triangle MN ′P has
the smallest diameter d with only once edge of length d, contradicting Lemma
2.4. By the cases in Figure 1, we can see that N = A or N = C as shown in
the Figure 2..
A = N
B
H2
M
H1
H1
C = NB M
P = H2
A
Figure 3. The case A = N and the case C = N
But the case N = A does not occur. If N = A then H2 is the midpoint of the
segment PA and the triangle MNH2 has the diameter d with only one edge
of length d, which contradicts Lemma 2.4.
Moreover, the case N = C can not be possible. If N = C then Ĉ ≥ 90◦ and
therefore H2 ∈ AB. By Lemma 2.1 using for MP instead of NP , we conclude
that P = H2. This leads to P̂MN > 90
◦ and therefore PN > PM =MN = d,
a contradiction to the assumption that PN < d.
The contradictions show that MNP is an equilateral triangle.
To estimate the smallest equilateral triangle in the given triangle ABC in
case b), we note that for every triangle ABC, assuming without loss of generality
Â ≥ max{B̂, Ĉ}, there exists a unique point I in the angle B̂AC , called eye-center,
such that ĈIA = B̂ + 60◦ and ÂIB = Ĉ + 60◦.
We prove the following theorem.
Theorem 2.2. Given a triange ABC, then the inscribed equilateral triang-le with
the smallest edge is the triangle formed by the feet of perpendicular dropped of the
eye-center I on the edges of ABC.
Proof. It is easy to prove that the triangle MNP is an equilateral triangle. Now,
let M ′N ′P ′ be an arbitrary equilateral inscribed triangle in the triangle ABC. By
Lemma 2.2, the circumscribed circles (ANP ), (BPM) and (CMN) are concurrent
37
Vu Dinh Hoa
B
A
C
B̂ + 60◦ Ĉ + 60◦
I
Figure 4. The eye-center
A
B
C
I
M
NP
Figure 5. The inscribed smallest equilateral triangle
in a point, called I ′. Let I ′A′, I ′B′ and I ′C ′ be the diameter or the circles (ANP ),
(BPM) and (CMN) respectively (Figure 2.). It is easy to see that I ′ is the eye-
center of the triangle A′B′C ′.
A′
B′M
′
N ′
C ′
A
B
P ′
C
I ′
Figure 6. The triangles ABC and A′B′C ′ are similar
Clearly, A′B′C ′ is a similar triangle to the triangle ABC and M ′N ′P ′ is an
inscribed triangle in A′B′C ′ where M ′, N ′ and P ′ are the feet of the perpendicular
dropped of I ′ onto the edges of A′B′C ′. Moreover, A′B′ ≥ AB by Lemma 2.3.
The dilation (with a quotient k ≤ 1), maping the triangle A′B′C” into triangle
ABC, maps I ′ to I (the eye-center of triangle ABC) since the eye-center is unique.
Therefore, this dilation maps M ′N ′P ′ to MNP and therefore the edges of M ′N ′P ′
is not shorter than the edges of MNP . Thus, the triangle MNP is the inscribed
38
Inscribed triangle with smallest diameter
equilateral triangle with smallest edges in ABC.
With similar argument, we easily get the same result for expanded problem
considering the three lines AB, BC and CA instead the edges of the given triangle.
Theorem 2.3. Let `1, `2 and `3 be three non-parallel lines. The inscribed triangle
MNP (M ∈ `1, N ∈ `2 and P ∈ `3) has the smallest diameter if and only if it is
the inscribed triangle with the smallest diameter in the triangle ABC formed by the
given lines.
For the case where some of the given lines are parallel, the smallest diameter
is clearly the largest distance of the parallel lines.
REFERENCES
[1] F. Aurenhammer, 1991. Voronoi Diagrams: A survey of a fundamental geometric
data structure. ACM Computing Surveys, No. 23.
[2] M. De Berg, M. Van Krefeld, M. Overmars, O. Schwarzkopf , 1998. Computa-
tional Geometry Algorithms and Applications. Springer.
[3] M. I. Shamos and D. Hoey, 1975. Closest point problem, In proc, 16 Annu. IEEE
Sympos, Found. Comput. Sci., pp. 151-162.
[4] Trung N.N, Huyen T.T.D, 1998. An algorithm for finding the closest pair of 2
colored points from a set of 2 colored points on plane. Journal of Natural Sciences,
HCM University of Pedagogy, No. 10, pp. 14-24.
[5] Trung N.N, Huyen T.T.D. A heuristic algorithm for finding the closest trio of
3-colored points from a given set of 3-colored points on plane, manuscript.
39