Question 13 Not yet answered Marked out of t ?Flag question Select the best answ
ID: 3920079 • Letter: Q
Question
Question 13 Not yet answered Marked out of t ?Flag question Select the best answer from among the given options: In the planar point location problem, a test point is glven (the query) and the answer to the query is this whether point is on the origin or not whether the point is equal to any of the present points or not which region on the plane the point is located which point on the plane it is closest to which line segment on the plane it is an endpoint of a. b. c. d. e. Select one: a. e b. C. o d. e. Question 14 Not yet answered Marked out of Remove flag Select the best answer from among the given options: We can construct the Voronoi diagrom for n sites in a sort of "brute-force" manner by intersecting n 1 halfplanes to produce each of the n Voronol regions. Since constructing the intersection of n halfplanes is dual to the task of constructing the convex hull of n points in 2D (and thus has the some time complexity), the Voronoi diagram can therefore be constructed in time. c.On IgnExplanation / Answer
Question 13:
The correct choice is C
Planar Point Location is a point location problem which preprocesses a planar subdivision such that for any test( query point) q , the face of subdivision that contains q can be obtained quickly.
hence it cannot be a. We arent concerned about origin.
Neither b,d or e are correct. The best answer is c
Question 14:
Construction of Vernoi Diagram for n sites in brute force manner will result in time complexity O(n2)
So the correct answer is (e)
Suppose you have to compute k-1 half space for given k points. Also you have to compute their intersection which is a (k-1)gon. By brute force, t comput kth half space we test k-1 interactions hence resulting in an overall O(n2) time complexity of constructing the diagram.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.