Report problems, Design and Analysis of Information Systems, '99

Problem 1　(very easy)

Place at least 10 points on a plane as you like, and draw its Voronoi diagram and Delauney triangulation.

Problem 2

Give your original ideas on 2-dimensional extension of "sorting" (exclusive the ones presented in my lectures)

Problem 3 (easy)

Given a convex polygon P, we would like to prepare a data structure such that we can detect the intersection with any given line $l$ in $O(\log n)$ time. What kind of data structure you construct and how you detect the intersection? Here, $n$ is the number of vertices of P.

Problem 4

　Point out defect or error in the solution of the following problem given below:
Problem: Given a convex polygon P with n vertices where n>4. Compute the quadlirateral with minimum area containing (i.e. circumscribing) P. 　　
Solution: Examine all combinations of four edges of P, and compute areas of the quadlirateral consisting of these edges (after extending them). Report the one with the minimum area.

Problem 5 (difficult)

Give an efficient solution on the above problem.　

Problem 6.

　Point out defect or error in the solution of the following problem given below:
Problem: Given a convex polygon P on a plane which rotate (360 degree per second around the center of gravity) and linearly move with a constant speed $v$.
We preprocess, and would like to compute the first collision time with the halfplane $y < 0$ efficiently for any given current position, angle, and the direction of movement. 　
Solution: For a given t>0, if the center of gravity is in the halfplane or P intersects the line $y=0$, P has already collided. Otherwise, P does not collide at $t$.
Thus, use it to do the binary search on $t$: If $t_0$ is the largest time that we did not detect collision and $t_1$ is the smallest time that we detected so far, we next examin $t_0 + t_1 /2$.

　Problem 7 (difficult)　　　　

Consider an efficient solution of the above problem, if you are permitted to have an error of 0.5 second for the reported collision time.　

Problem 8

　Summarize　the basic operations on 2-3 tree --- Search,　Insert, Delete (at most five A4 papers).

Problem 9

　Devise an algorithm for computing three dimensional convex hull by yourself and analyze it.

Problem 10

Summarize on your favorite topic on comuter science so that I (Tokuyama) can easily understand.