Computational geometry for polygonal reconfiguration, pattern analysis and recognition and music information retrieval

点击翻译按钮获取中文摘要

The proposed research aims to develop efficient algorithms for solving geometric problems that arise in the following areas. (1) The exploration of algorithms for the reconfiguration of different types of linkages in 2 and 3 dimensional space, under various restrictions on the types of motions allowed. Another goal is to explore under what conditions linkages are "stuck" in the sense that they cannot be reconfigured to a flat convex configuration. These results are relevant, not only to robotics, but to protein folding in molecular biology. (2) One of the most promising approaches to pattern recognition is the nearest-neighbor decision rule (also referred to as instance-based learning). It is proposed to improve the space and time efficiency of state-of-the-art nearest neighbor rule algorithms, by incorporating proximity graphs. A second objective is to develop new measures of string similarity and polygonal chain similarity for pattern recognition problems. (3) It is proposed to explore the application of computational geometric tools to problems that arise in music information retrieval and music theory. These problems range from measuring the similarity of rhythms and melodies, to performing cluster and phylogenetic analyses of families of rhythms, with the goal of obtaining a deeper understanding of both, music theory and practical applications to music information retrieval. (4) Traditionally the scientific analysis of textiles has been carried out on several physical structural levels of the fabrics. However, a scientific analysis of the geometric structure of the patterns that appear on the textiles has been largely ignored. We propose a new approach to the scientific study of textiles that breaks with this tradition: the phylogenetic analysis of geometric patterns that decorate the textiles. At the heart of our approach is the design of a measure of dissimilarity between two textile patterns, that mimics the way in which biologists measure the dissimilarity between two DNA molecular sequences, i.e., the minimum number of mutations (simple local and global transformations) required to transform one textile pattern into the other. This research will have an impact of image-based search on the internet, as well as textile retrieval systems for use in museums and libraries.