Teaching the Nearest Neighbor Search Problem in an Undergraduate Algorithm Analysis Course.pdfVIP

Teaching the Nearest Neighbor Search Problem in an Undergraduate Algorithm Analysis Course Sun B. Chung Department of Quantitative Methods and Computer Science University of St. Thomas St. Paul, MN 55 124 sbchung @stthomas.edu Abstract The nearest neighbor search problem is an important problem in computer science that has a wide range of applications including medical image processing, pattern recognition, mobile computing, and retrieval of multimedia obj ects such as images, text, and videos over the Internet. The problem deserves more attention than it receives in undergraduate computer science education for the following reasons. First, it has a wide range of applications in areas that are relevant to our daily lives. Second, it has interdisciplinary applications such as medical image processing, so it will provide a good opportunity for students to appreciate the contributions that theoretical computer science can make in practical areas. Third, the exact and approximate algorithms for the problem and its variants will provide students with interesting materials for comparison and analysis. In this paper, I propose a way to incorporate the nearest neighbor search problem in an “analysis of algorithms” course. 1 Introduction In computer science, there is an important problem called nearest neighbor search. The problem can be described informally with the following example: Place a pin on the map of the U.S. What is the nearest city to the pin? The problem deals with a 2-dimensional space, and it is easy to find a solution for such a low dimension. However, in high dimensional spaces, typically greater than 25 dimen