Chinese name: The minimum Manhattan network problem was put forward by J. Gudmundsson, C. Levkoplos and G. Na Lassime Han: 1999? Scope of application: briefly describe network design and urban planning, history, background, problems, solutions, difficulties, progress and achievements, and briefly describe a point set T on a given plane, and its Manhattan network consists of horizontal and vertical line segments, which meets the requirement that Manhattan paths exist in the network between any two points in T. It is known that Manhattan network is a 1- wrench of a given point set under L 1- norm. The more general concept is called geometric wrench or K-wrench. Because of its good properties, it is widely used, including the solution of its proximity problems, robot motion planning, the reliability of communication networks and so on. In this problem, the total length of line segments in Manhattan network is required to be the shortest, that is, the Manhattan network with a given set of points is constructed at the minimum cost. In addition, F. Lam and others applied the approximate algorithm of Manhattan Network in the biological sequence alignment problem, which significantly reduced the search space. This shows the application of minimum Manhattan network problem in computational biology. Therefore, the research on this issue has important theoretical and practical significance. The smallest Manhattan network problem in history is an important conjecture of world-class computational geometry proposed by 1999. In 1999, J. Gudmundsson, C. Levkopoulos and G. Na Lassime Han first proposed the minimum Manhattan network problem. Since then, many scholars have studied and given polynomial time approximation algorithm for this problem. The best approximation algorithm (3- approximation) designed by combination method was given by M. Benkert and others in 2004. In 2005, V. Chepoi and others proposed a 2- approximation algorithm based on linear programming, which is the best approximation known at present. In June 2009, Guo Zeyu, a junior in the School of Computer Science of Fudan University, was hired by the 25th International Conference on Computational Geometry for his paper "Minimum Manhattan Network Problem". At the same time, as one of the best papers, this paper was invited to contribute to the conference special issue "Discrete Computational Geometry" (DCG). It means that the important conjecture from ten years in computational geometry has been successfully solved by this 20-year-old undergraduate. The International Conference on Computational Geometry is the highest-level conference in the field of computational geometry, and it has been 18 years since mathematicians in Chinese mainland left. Minimum background Manhattan network problem is an important conjecture of world-class computational geometry proposed by 1999. In 1999, J. Gudmundsson, C. Levkopoulos and G. Na Lassime Han first proposed the minimum Manhattan network problem. Since then, many scholars have studied and given polynomial time approximation algorithm for this problem. The best approximation algorithm (3- approximation) designed by the above combination method was given by M. Benkert and others in 2004. In 2005, V. Chepoi and others proposed a 2- approximation algorithm based on linear programming, which is the best approximation of the known problem. In June 2009, it was successfully solved by Guo Zeyu, a 20-year-old undergraduate from Fudan University in Shanghai. His paper on "Minimum Manhattan Network Problem" was accepted by the 25th International Conference on Computational Geometry, and as one of the best papers, he was invited to contribute to the special issue of Discrete and Computational Geometry (DCG). The Manhattan net of point set T on a given plane is composed of horizontal and vertical line segments, which satisfies that there is a Manhattan road between any two points in T. It is known that Manhattan net is a 1- wrench for a given point set under L 1- norm. The more general concept is called geometric wrench or K-wrench. Because of its good properties, it has a wide range of applications, including the solution of proximity problems, the motion planning of robots, the reliability of communication networks and so on. In this problem, the total length of line segments in Manhattan network is required to be the shortest, that is, the Manhattan network with a given set of points is constructed at the minimum cost. In addition, F. Lam and others applied the approximate algorithm of Manhattan Network in the biological sequence alignment problem, which significantly reduced the search space. This shows the application of minimum Manhattan network problem in computational biology. The solution is to design an approximation algorithm with better approximation. The design methods of approximate algorithm mainly include: local search method, linear programming method, primal-dual method and so on. The known approximation algorithms for this problem can be divided into two categories: one is to simplify the global optimal network problem to a local optimal network problem, and then achieve the global optimal solution through the combination of local networks, such as the 3- approximation algorithm proposed by M. Benkert and others. In the application of this method, Guo Zeyu has achieved international leading results. The other is based on linear programming, such as the 2- approximation algorithm proposed by V. Chepoi and others in the literature. In the first stage of research, on the one hand, on the basis of the known optimal approximation algorithm, the essence of the problem is analyzed in detail, trying to improve it; On the other hand, the design of approximate algorithm is studied systematically and other algorithm design ideas are explored. Research on the complexity of the problem Although the minimum Manhattan network problem has attracted the attention of many western computer scientists in the past decade, it is not clear whether there is a polynomial time algorithm for this problem. People suspect that this problem is NP-complete, but so far no one has given an effective proof. Generally speaking, the basic method to prove that a problem is NP-complete is to simplify a known NP-complete problem into the problem under study. In this respect, the known NP-complete computational geometry and the reduction process of combinatorial optimization problems will have great reference value. For example, the RSA problem mentioned by V. Chepoi is quite similar to the minimum Manhattan network problem, and W.Shi and C. Su have given the reduction from Planar-3-SAT problem to this problem, thus proving that this problem is NP-complete. Therefore, Guo Zeyu has mastered all kinds of complicated skills by reading more articles on NP- complete problem specification in computational geometry. This paper attempts to give a similar reduction method for the minimum Manhattan network problem, thus proving that this problem is NP-complete. Whether the least difficult Manhattan network problem is NP- hard or unknown, its non-approximation is not clear. Therefore, studying the complexity category of this problem will have important theoretical significance and practical value. It is unrealistic for Guo Zeyu to solve the NP-hard problem of minimum Manhattan network algorithm complexity, but it is a feasible research direction to improve the efficiency of existing solutions or improve the approximation. Guo Zeyu's result is 2- approximate O(n2) time complexity. Can the efficiency be improved to O(nlogn), just like the 3- approximation method? Or the new method of 1.5- approximation is a new problem to be solved urgently. On June 2, 2009, the news came from Fudan University. Guo Zeyu, a junior in Computer College, was hired by the 25th International Conference on Computational Geometry sponsored by ACM Society of the United States, and the article was also invited as one of the excellent papers to be submitted to DCG. This means that the 20-year-old undergraduate has successfully solved an important conjecture that has not been solved in the field of computational geometry for more than ten years. In June, 2008, Guo Zeyu applied for the "Zheng Zheng" project, an undergraduate academic research funding project of Fudan University. The Minimum Manhattan Network Problem is a topic given to his undergraduates by Professor Hong Chu of Computer College. Guo Zeyu boldly chose this issue as the research object of the subject. This not only makes two project instructors, Professor Hong Chu and Dr. Sun He, happy, but also worries the experts of "Zheng Zheng" scholars. Based on the consideration of encouraging undergraduates to innovate and supporting young people to start businesses, Guo Zeyu was finally funded. After more than 200 days and nights of thinking and exploration, this problem was finally discovered by it. Among the achievements in the field of algorithm research, people are most concerned about those long-standing unresolved problems. "Manhattan network problem" is such a problem, it is not clear whether it is P or NP. There is an approximation algorithm with an approximation degree of 2, but its complexity is O (n 8). Guo Zeyu reformed the algorithm. It is commendable to accelerate it to O (n 2). Therefore, it was accepted as the report of the international conference, reflecting the importance attached to it by peers. Manhattan network problem is an important topic in computer theory research. Guo Zeyu's research on the minimum Manhattan network algorithm complexity has theoretical significance and practical value. Since there is no clear conclusion whether Manhattan network problem is NP-hard, the research on Manhattan network problem mainly focuses on approximate algorithm. Guo Zeyu improved the existing 2- approximation algorithm under the guidance of his tutor, making its time complexity reach O(n2) (the original algorithm was O(n8)). This project has a good research foundation and is expected to obtain further innovative results. Minimum Manhattan Network Problem —— How does Guo Zeyu solve the minimum Manhattan network problem? In June, 2008, Guo Zeyu applied for the "Zheng Zheng" project, an undergraduate academic research funding project of Fudan University. The Minimum Manhattan Network Problem is a topic given to his undergraduates by Professor Hong Chu of Computer College. Guo Zeyu boldly chose this issue as the research object of the subject. This not only makes Professor Hong Chu and Dr. Sun He happy, but also makes the experts of "Zheng Zheng" scholars worry. Based on the consideration of encouraging undergraduates to innovate and supporting young people to start businesses, Guo Zeyu was finally funded. After more than 200 days and nights of thinking and exploration, he finally found a breakthrough in this difficult problem. It is reported that the International Conference on Computational Geometry is the highest-level conference in the field of computational geometry, which has been far away from China Mathematicians 18 years. In Guo Zeyu's project application, Lu Ruqian, an academician of Chinese Academy of Sciences, as a recommended teacher, fully affirmed the undergraduate academic research funding scheme. He believes that many students stand out in this way and embark on the road of scientific research. The reporter learned that 1998 With the support of the "Zheng Zheng Fund" initiated and established by Mr. Li Zhengdao, Fudan University began to subsidize outstanding undergraduates to get in touch with academic research as soon as possible, and gradually formed a well-defined undergraduate academic research funding platform with flexible application time and various application forms, namely the Fudan University Undergraduate Academic Research Funding Plan. From 1998 to 2008, * * 1556 students were funded to carry out research, and their project disciplines covered many fields such as medicine, engineering, science, literature and education. According to incomplete statistics, in 2008, students who participated in Fudan University's undergraduate academic research funding project published 30 papers in domestic and foreign journals, including 20 first authors.