推 chuo:kd-tree是什麼 05/23 21:24
多少有人會幾題吧~~救命...
1. (15%)
(a) we introduced the d-dimensional kd-tree and mentioned that a query takes O(n^(1-1/d) + k) time.
the purpose of thisquestion is to give a proof that the query time is the value as stated
above.
(b) In the middle of Lecture Voronoi Diagrams, we claim that V(si) is unbounded iff si is
a vertex of CH(S). However, we did not give the proof for it in our
lecture. Please give a proof for this claim.
2. (35%) Kd-trees can be used for partial match queries. A 2-dimensional
partial match query specifies a value for one of the coordinates and asks
for all points that have that value for the specified coordinate. In higher
dimensions, we specify values for a subset of the coordinates. Here we
allow multiple points to have equal values for coordinates.
(a) Show that 2-dimensional kd-trees can answer partial match queries
in O(pn + k) time, where k is the number of reported answers.
(b) Explain how to use a 2-dimensional range tree to answer partial
match queries. What is the resulting query time?
(c) Describe a data structure that uses linear storage and solves 2-dimensional
partial match queries in O(log n + k) time.
(d) Show that with a d-dimensional kd-tree, we can solve a d-dimensional
partial match query in O(n^(1-s/d)+k) time, where s (with s < d) is the
number of specified coordinates. Please describe clearly your query
procedure, and give the proof for the query time.
(e) Describe a data structure that uses linear storage and that can answer
d-dimensional partial match queries in O(log n + k) time.
Hint: Use a structure whose dependence on d in the amount of storage
is exponential (more precisely, a structure that uses O(d2dn) storage).
3. (25%)
(a) In Lecture 7, we have characterized the Voronoi diagram of two
points. In this question, please characterize the Voronoi diagram
of two disjoint non-parallel line segments. Explain your characterization.
(b) This question is about the Fortune’s algorithm of Lecture 7. Do
the breakpoints of the beach line always move downwards when the
sweep line moves downwards? Prove this or give a counterexample.
(c) Again this question is about the Fortune’s algorithm of Lecture 7.
Give an example where the parabola defined by some site pi contributes
more than one arc to the beach line. Can you give an example
where it contributes a linear number of arcs?
4. (25%)
(a) Let L be a set of n lines in the plane. Give an O(n log n) time
algorithm to compute an axis-parallel rectangle that contains all the
vertices of A(L) in its interior.
(b) The dual transform we learned from our lecture has minus signs.
Suppose we change them to plus signs, so the dual of a point (px, py)
is the line y = pxx + py, and the dual of the line y = mx + b is the
point (m, b). Is this dual transform incidence-preserving and order
reversing?
(c) Let S be a set of n points in the plane. Give an O(n2) time algorithm
to find the line containing the maximum number of points in S.
5. (20%) The Gabriel graph of a set P of points in the plane is defined as
follows: Two points p and q are connected by an edge of the Gabriel graph
if and only if the circle with diameter pq does not contain any other point
of P in its interior.
(a) Prove that DT (P) contains the Gabriel graph of P.
(b) Prove that p and q are adjacent in the Gabriel graph of p if and only
if the Delaunay edge between p and q intersects its dual Voronoi edge.
(c) Give an O(n log n) time algorithm to compute the Gabriel graph of
a set P of n points.
6. (20%) The Euclidean traveling-salesman problem is the problem of determining
the shortest closed tour that connects a given set of n points in the
plane. The general problem is NP-complete. J. L. Bentley has suggested
the problem by restricting our attention to bitonic tours, that is, tours
that start at the leftmost point, go strictly left to right to the rightmost
point, and then go strictly right to left back to the starting point. (Equivalently,
any vertical line should cross the tour at most twice.)
Describe an O(n2)-time algorithm for determining an optimal bitonic tour.
You may assume that no two points have the same x-coordinate.
(Hint: Scan left to right, maintaining optimal possibilities for the two parts
of the tour.)
※ 引述《chuo (v(￣︶￣)y)》之銘言：
: ※ 引述《jimmychad (吉米)》之銘言：
: : 誰來救救我~~有人會的嗎?
: : http://140.114.78.101/jimmychad/1.jpg
: : 題目應該看的懂吧~~看起來是奇聰的major
: 回文會有紅勾勾 比較明顯
: 可是...我都不會 Orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.85.62