# 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\$B!!(B(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
\$B!!(BPoint 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. \$B!!!!(B
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.\$B!!(B
Problem 6.
\$B!!(BPoint 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. \$B!!(B
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\$.
\$B!!(BProblem 7 (difficult)\$B!!!!!!!!(B
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.\$B!!(B
Problem 8
\$B!!(BSummarize\$B!!(Bthe basic operations on 2-3 tree --- Search,\$B!!(BInsert, Delete (at most five A4 papers).
Problem 9
\$B!!(BDevise 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. \$B!!(B