Report problems, Design and Analysis of Information Systems'01

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.