D Lee - US grants

This is work on optimization problems that arise in computational geometry and related areas. Problems are being studied in four areas: covering and approximation; minimum diameter spanning trees; via minimization; and, proximity and visibility. These problems have applications in areas such as computer-aided design, computer graphics, operations research, and robotics. The emphasis in this project is on the design of efficient algorithms for the problems under consideration.

This is an 18 month cooperative research project proposed by Dr. Der-Tsai Lee, Northwestern University and Professor R.C.T. Lee, Taiwan Tsing Hua University, supported by the AIT (U.S.) - CCNAA (Taiwan) Cooperative Science Program. This project plans to study ways to minimize the paths between the points in one segment of a computer disk and those in another segment. This is an important problem in geometric optimization and computer computation. Professor Lee of Tsing Hua University is an expert in this area with the additional human and funding resources needed to carry out computer simulations. This is a mutually beneficial study of a set of problems for which there are currently no solutions. Advances in this area can benefit computing and automation industries.

Optimization problems that arise in computational and other related areas are investigated in this project. Special emphasis is placed on bi-criteria optimization problems and geometric problems. In a communication network, the two important criteria that are of great practical implications are the communication delay and total cost. In path planning routing, the two important criteria are the total length and the number of bends. Optimization problems concerning two criteria either simultaneously or in lexicographical order are studied. Among those to be studied are weighted farthest neighbor Voronoi diagram construction for a set of point sites, a new class of geometric problems, called the capacitated path problem, in which the obstacles have capacities and the cost of a path avoiding these obstacles is a function of the length of the path and the capacities of the obstacles visited by the path, and routing problems with multiple source-destination pairs such that these paths do not cross and yet their total length is to be minimized. The goals of this research are to apply geometric techniques to tackle these new classes of optimization problems, and to identify problems that can (or cannot) benefit from the geometric properties.

CDA-9703228 Prithviraj Banerjee Northwestern University A Distributed High-Performance Computing Infrastructure This award is for the acquisition of 20 high-end UNIX workstations, 50 low-end UNIX workstations, three UNIX fileservers, an 8-processor distributed shared memory multiprocessor, and a 64-ported ATM switching hub. The machines would be networked together using high-speed OC-3 ATM networks with bandwidths of 155 Mbps. As the use of high-speed networking moves from the laboratory to the workplace, new opportunities arise for the design and implementation of a high-speed distributed computing environment. The goals of this project are: (1) to explore the use of high-speed networking and computing to investigate file systems and data management issues for high-performance distributed computing, (2) to investigate the parallel programming support of networks of high-speed workstations and personal computers as an alternative to stand-alone parallel computers, (3) to study high-performance computer-aided design of electronic systems in a heterogeneous environment, and to develop a Web-based CAD computing center, that takes advantage of high-speed networking, (4) to explore new instructional techniques that take advantage of the high bandwidth and high speed.