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 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.