Report problems, Design and Analysis of Information Systems, '99
Select three among the following problems, and report the solutions.
Deadline: February 15 (nice if you can submit earlier)
 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 2dimensional 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 23 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.