Report problems, Design and Analysis of Information Systems'01

Deadine:February 14, 2002.
Original ideas are highly appreciated
Problem 1.
Develop a data structure for querying the nearest $L_1$ neighbor in a set of $n$ points.
Problem 2.
Given $n$ obstacle points in a rectangle. We have a robot at a place $A$ in the rectangle, and would like to move it to a place $B$. Design an algorithm to detect whether we can move the robot without colliding the obstacle points, if the robot is a disk of radius $r$.
Problem 3.
What happens if the robot is a triangle and cannot rotate.
Problem 4.
Give an idea to solve the problem if the robot can rotate about its center of gravity.
 Problem 5.
Explain a problem in computer science that you are now interested in, so that Tokuyama can understand easily.