再鑽一次錢
1(a) Q(n)=2^(d-1)+2^(d-1)*Q(n/2^d) by mater theory =>O(n^(1-1/d))
so answer the query takesO(n^(1-1/d)+k) where k is the number of return.
1(b)The Voronoi region of p is unbounded i there exists some point q belongs
to S such that V (S) contains an unbounded piece of B(p; q) as a Voronoi edge.
where B(p,q)={x where d(p,x)=d(q.x)},p,q 屬於S,d(x,y)是由拉距離. Let x belongs
to B(p; q), and let C(x) denote the circle through p and q centered at x,
Point x belongs to V (S) iff C(x) contains no other site. As we move x to the
right along B(p; q), the part of C(x) contained in halfplane R keeps growing.
If there is another site r in R, it will eventually be reached by C(x),
causing the Voronoi edge to end at x. Otherwise, all other sites of S must be
contained in the closure of the left halfplaneL. Then p and q both lie on
the convex hull of S.
希望這次作業也能掰到90~~
油價漲了 要來這裡賺錢@@
※ 引述《jimmychad (吉米)》之銘言：
: 讓我來賺一下錢
: 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.)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.98