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