Re: [請益] 十萬火急十萬火急
讓我來賺一下錢
K-D tree:http://en.wikipedia.org/wiki/K-d_tree
複製一大推又賺少少錢
要我打字又太花時間
沒有其他賺錢的方法嗎?
※ 引述《jimmychad (吉米)》之銘言：
: 多少有人會幾題吧~~救命...
: 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)》之銘言：
: : 回文會有紅勾勾 比較明顯
: : 可是...我都不會 Orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.85.156
討論串 (同標題文章)