9603605 Agarwal This award provides funds to permit Dr. Pankaj K. Agarwal, Department of Computer Science, Duke University, to pursue with Dr. Otfried Schwarzkopf, Pohang. University of Science and Technology, (POSTECH), Pohang, Korea for 36 months, a program of cooperative research on efficient geometric algorithms and their applications. These collaborators will study the following areas in computational geometry: randomized algorithms, approximation algorithms, arrangements of curves and surfaces, multidimensional searching, robot motion planning and collision detection, and proximity problems. Computational geometry concerns itself with the design, analysis, and implementation of geometric algorithms. Problems in several applied areas including graphics, computer vision, pattern recognition, image processing, medical imaging, robotics, data mining, and geographical data processing have motivated the study of a number of geometric problems from a computational point of view, and their efficient solutions often require sophisticated techniques from computer science and various mathematical disciplines. The PI and his collaborator in Korea have made significant contributions to many basic and applied problems in the area, including motion planning, computer graphics, randomized algorithms, the study of arrangements of curves and algebraic surfaces and data structures for multidimensional searching. The purpose of the present project is to continue such research and to initiate new collaboration in computational geometry. The emphasis will be on developing simple and practical algorithms, on cross-fertilization between basic research and the various applications, on understanding higher dimensional problems, and on handling curved objects. This project is relevant to the objectives of the U.S.-Korea Cooperative Science Program, which seeks to increase the level of cooperation between U.S. and Korean scientists and engineers through the exchange of scientific information, ideas, skills, an d techniques and through collaboration on problems of mutual benefit. This project provides an international research experience for an U.S. graduate student Korean participation is supported by the Korea Science and Engineering Foundation (KOSEF). ***
