Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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. | 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 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 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
