OUTLIER IDENTIFICATION AND HANDLING IN COMPUTATIONAL GEOMETRY PROBLEMS Computational geometry problems arise in all areas of science and engineering, in contexts such as computer vision, machine learning, data mining, classification, data compression, geographic information systems, clustering, and facility location. Advances in computational geometry can yield advances in robotics, genomics, and proteomics, to mention three areas of pressing interest. Increasing concern in computational geometry problems is being devoted to outliers, points in the input data whose removal can yield significant improvements in attainable optimal values of objective functions. Recent treatments giving attention to outliers involve quite appealing methods with good results, but these have been ad hoc solutions, specific to particular problem contexts and entailing restrictive assumptions. It would be desirable to derive such approaches in a systematic manner from general principles and guidelines, and to evaluate and compare outlier procedures on such a basis. To date, however, no systematic approach for handling outliers in computational geometry problems has been set forth, nor has there been advanced a set of specific criteria to be satisfied by outlier procedures. Through interdisciplinary collaboration between a computer scientist and a statistical scientist, this project will develop an outlier identification and handling approach as a new and versatile tool in computational geometry. Structures of a general nature for effective outlier identifiers will be formulated. Criteria to be satisfied and desirable qualitative features will be formulated. Issues such as robustness of outlier identifiers will be addressed. Efficient computing algorithms will be developed. Significant restrictions on current approaches will be relaxed. The project will focus on outlier handling in shape fitting and dimension reduction prob- lems. A leading tool will be depth functions, an emerging methodology in nonparametric multivariate data analysis that is useful for description of distributions and data sets and in- herently supports characterization of outlyingness for points in a data input. As a byproduct, the project will obtain advances in depth function methods as well. One proposer has been developing efficient algorithms in computational geometry, the other developing depth and outlier methods in multivariate data analysis. One proposer co- organized, and both proposers participated in, the recent NSF-sponsored Workshop on Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications (DIMACS, 2003), which fostered the collaboration for this research project. The leading intellectual merit of this project is to advance the foundations of computer science by providing a general and fundamental method that replaces ad hoc approaches to outlier handling. Also, the findings will advance the field of statistical science in the area of nonparametric multivariate data analysis. Broader impacts of the project include strengthening of the interface between computer science and statistical science and involvement of graduate and undergraduate students within a team approach as part of their academic experience. Through its wide applica- bility the findings of this project will have immediate and central relevance to many areas of science, engineering and government. The PIs will maintain a web site on which project results are made known and available to the public at large.
