Question

Please resolve the three issues below:

28. The pathological case given below illustrates 30. Kirkpatrick's remorkable algorihnfor planar that the complexity of a planar subdivision into slabs can be this bad: point location is optimal in this respect a. It matches the lower bound to the worst-case performance for all search algorithms of 2lg n). b. It requires OKn) space which is optimal since the input is of the same order in size. c. It requires On) time in constructing the hierarchical tree structure, which is optimal since the size of the tree structure is also On) d. All of these (i.e., all are optimality criteria). e. The algorithm is not optimal at all a· 0(Ign) b. O(n) c. On Ig n) 29. Kirkpatrick's remarkable algorithm for planar point location involves the following "ingredients", except: a. Constructing a hierarchical tree structure of successively "sparser" triangulations b. Recursive descent in the tree structure involving testing for inclusion in triangles Fully triangulating the given planar straight line graph as a preprocessing step c. d. None of these (i.e,, all are ingredients) e. All of these (i.e., none are ingredients).

Answer 1

Q28) b) O(N) [the complexity of a planar subdivision is O(nv), i.e., linear in the number of vertices]

Q29) d) None of these (All are ingredients)

Q30) a) It matches the lower bound to the worst case performance for all search algorithms of Omega (log n)

Please let me know in case of any clarifications required. Thanks!