Nội dung

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 3colored 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 M N P 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 differentcolored 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 triangle MNP with M ∈ BC, N ∈ CA and P ∈ AB such that the diameter of MNP 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 P N > NM. If NH ∩ AC 6= {N} then there exists N 0 6= N on AC such that P N 0 < P N and N 0 M < P N. 1. Note that NH ∩ AC = {N} occurs only in one of the following cases in Figure H A=N P B P C B A H=N C A P B C=N H 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 ), (BP M) 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 O1 O2 . 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 0 ∈ AC such that P N 0 < P N and MN 0 < P N and therefore the triangle MN 0 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 0 ∈ AB such that P 0 N < P N and P 0 M < P N and therefore the triangle MNP 0 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 b B, b C} b ≥ 120◦, say A b ≥ 120◦ , then the inscribed triangle with smalla) If max{A, b and est diameter is the triangle MNP , where AM is the bisector of angle A N and P are the feet of the perpendicular dropped of M onto the edges AC and AB respectively. b B, b C} b then the inscribed triangle with the smallest diameter b) If 120◦ ≥ max{A, is the inscribed equilateral triangle with the smalles edge. b ≥ 120◦ we have P\ Proof. a) Since A MN ≤ 60◦ , thus MP = MN ≥ P N. Now 0 0 0 let M N P be an arbitrary inscribed triangle in triangle ABC (see Figure 2). Without loss of generality suppose that M 0 ∈ MC. Then M 0 H 0 ≥ MP where H 0 is the foot of the perpendicular dropped from M 0 onto the line AB. Clearly, M 0 P 0 ≥ M 0 H 0 ≥ MP and thus the diameter of the triangle M 0 N 0 P 0 is greater than the diameter of the triangle MNP . P B 0 P A H0 N N0 M M0 C b ≥ 120◦ Figure 2. The case A 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 b ≤ 120◦ . Thus, we can suppose that H1 6= N NP < MP = MN = d and A (the case H2 6= P is similar). By Lemma 2.1 using for MN and NP instead of P N and NM, we have H1 N ∩AC = {N}, since by otherwise we can choose an point N 0 such that P N 0 < NM and N 0 M < NM and the triangle MN 0 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.. H2 H1A = N A P = H2 C=N H1 Figure 3. The case A = N and the case C = N B M B M But the case N = A does not occur. If N = A then H2 is the midpoint of the segment P A and the triangle MNH2 has the diameter d with only one edge of length d, which contradicts Lemma 2.4. b ≥ 90◦ and Moreover, the case N = C can not be possible. If N = C then C 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 P N > P M = MN = d, a contradiction to the assumption that P N < 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 b ≥ max{B, b C}, b there exists a unique point I in the angle BAC, [ called eye-center, A b + 60◦ and AIB b + 60◦ . [=B [=C such that CIA 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 0 N 0 P 0 be an arbitrary equilateral inscribed triangle in the triangle ABC. By Lemma 2.2, the circumscribed circles (ANP ), (BP M) and (CMN) are concurrent 37 Vu Dinh Hoa I b b + 60◦ B + 60◦ C C B A Figure 4. The eye-center A P N I B M C Figure 5. The inscribed smallest equilateral triangle in a point, called I 0 . Let I 0 A0 , I 0 B 0 and I 0 C 0 be the diameter or the circles (ANP ), (BP M) and (CMN) respectively (Figure 2.). It is easy to see that I 0 is the eyecenter of the triangle A0 B 0 C 0 . A A0 N0 I0 C0 C M0 P0 B B0 Figure 6. The triangles ABC and A0 B 0 C 0 are similar Clearly, A0 B 0 C 0 is a similar triangle to the triangle ABC and M 0 N 0 P 0 is an inscribed triangle in A0 B 0 C 0 where M 0 , N 0 and P 0 are the feet of the perpendicular dropped of I 0 onto the edges of A0 B 0 C 0 . Moreover, A0 B 0 ≥ AB by Lemma 2.3. The dilation (with a quotient k ≤ 1), maping the triangle A0 B 0 C” into triangle ABC, maps I 0 to I (the eye-center of triangle ABC) since the eye-center is unique. Therefore, this dilation maps M 0 N 0 P 0 to MNP and therefore the edges of M 0 N 0 P 0 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. Computational 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