# Computational Geometry in Data structure and Algorithms MCQs

Q1. What will be the slope of the line given by ax + by + c = 0?.

A.  -a/b.

B.  -b/a.

C.  -c/a.

D.  a/c.

Q2. What will be the slope of the line given by 10x + 5y + 8=0?.

A. -5.

B. -2.

C. -1.25.

D. 5.

Q3. What will be the co-ordinates of foot of perpendicular line drawn from the point (-1,3) to the line 3x-4y-16=0?.

A.  (1/5,2/5).

B.  (2/25,5/25).

C.  (68/25,-49/25).

D.  (-49/25,68/25).

Q4. Which of the following is used to find the absolute value of the argument in C++?.

A.  abs().

B.  fabs().

C.  mod().

D.  ab().

Q5. What will be the slope of the line perpendicular to the line 6x-3y-16=0?.

A.  1/2.

B.  -1/2.

C. 2.

D. -2.

Q6. Which of the following areas do closest pair problem arise?.

A.  computational geometry.

B.  graph colouring problems.

C.  numerical problems.

D.  string matching.

Q7. Which approach is based on computing the distance between each pair of distinct points and finding a pair with the smallest distance?.

A.  Brute force.

B.  Exhaustive search.

C.  Divide and conquer.

D.  Branch and bound.

Q8. What is the runtime efficiency of using brute force technique for the closest pair problem?.

A.  O(N).

B.  O(N log N).

C.  O(N^2).

D.  O(N3 log N).

Q9. The most important condition for which closest pair is calculated for the points (pi, pj) is?.

A.  i>j.

B.  i!=j.

C.  i=j.

D.  i<j.

Q10. What is the basic operation of closest pair algorithm using brute force technique?.

A.  Euclidean distance.

C.  Area.

D.  Manhattan distance.

Q11. Which of the following is similar to Euclidean distance?.

A.  Manhattan distance.

B.  Pythagoras metric.

C.  Chebyshev distance.

D.  Heuristic distance.

Q12. What is the optimal time required for solving the closest pair problem using divide and conquer approach?.

A.  O(N).

B.  O(log N).

C.  O(N log N).

D.  O(N^2).

Q13. In divide and conquer, the time is taken for merging the subproblems is?.

A.  O(N).

B.  O(N log N).

C.  O(N^2).

D.  O(log N).

Q14. Cross product is a mathematical operation performed between ________________.

A.  2 scalar numbers.

B.  a scalar and a vector.

C.  2 vectors.

D.  any 2 numbers.

Q15. Cross product is also known as?.

A.  scalar product.

B.  vector product.

C.  dot product.

D.  multiplication.

Q16. The concept of cross product is applied in the field of computer graphics..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q17. Which of the following equals the a x b ( a and b are two vectors)?.

A.  – (a x b).

B.  a.b.

C.  b x a.

D.  – (b x a).

Q18. Cross product of two vectors can be used to find?.

A.  area of rectangle.

B.  area of square.

C.  area of parallelogram.

D.  perimeter of rectangle.

Q19. The resultant vector from the cross product of two vectors is _____________.

A.  perpendicular to any one of the two vectors involved in cross product.

B.  perpendicular to the plane containing both vectors.

C.  parallel to to any one of the two vectors involved in cross product.

D.  parallel to the plane containing both vectors.

Answer=  perpendicular to the plane containing both vectors

Q20. What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k?.

A.  i + 2j + k.

B.  2i + 3j + k.

C.  i – j – 5k.

D.  2i – j – 5k.

Answer=  i – j – 5k

Q21. What will be the cross product of the vectors 2i + 3j + k and 6i + 9j + 3k?.

A.  i + 2j + k.

B.  i – j – 5k.

C. 0.

D.  2i – j – 5k.

Q22. Which of the following operation will give a vector that is perpendicular to both vectors a and b?.

A.  a x b.

B.  a.b.

C.  b x a.

D.  both a x b and b x a.

Answer=  both a x b and b x a

Q23. ___________ is a method of constructing a smallest polygon out of n given points..

A.  closest pair problem.

B.  quick hull problem.

C.  path compression.

D.  union-by-rank.

Q24. What is the other name for quick hull problem?.

A.  convex hull.

B.  concave hull.

C.  closest pair.

D.  path compression.

Q25. How many approaches can be applied to solve quick hull problem?.

A. 1.

B. 2.

C. 3.

D. 4.

Q26. What is the average case complexity of a quick hull algorithm?.

A.  O(N).

B.  O(N log N).

C.  O(N^2).

D.  O(log N).

Q27. What is the worst case complexity of quick hull?.

A.  O(N).

B.  O(N log N).

C.  O(N^2).

D.  O(log N).

Q28. Which of the following statement is not related to quickhull algorithm?.

A.  finding points with minimum and maximum coordinates.

B.  dividing the subset of points by a line.

C.  eliminating points within a formed triangle.

D.  finding the shortest distance between two points.

Answer=  finding the shortest distance between two points

Q29. The quick hull algorithm runs faster if the input uses non- extreme points..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q30. To which type of problems does quick hull belong to?.

A.  numerical problems.

B.  computational geometry.

C.  graph problems.

D.  string problems.

Q31. Which of the following algorithms is similar to a quickhull algorithm?.

A.  merge sort.

B.  shell sort.

C.  selection sort.

D.  quick sort.

Q32. Who formulated quick hull algorithm?.

A.  Eddy.

B.  Andrew.

C.  Chan.

D.  Graham.

Q33. The time is taken to find the ‘n’ points that lie in a convex quadrilateral is?.

A.  O(N).

B.  O(N log N).

C.  O(N^2).

D.  O(log N).

Q34. Chan’s algorithm is used for computing _________.

A.  Closest distance between two points.

B.  Convex hull.

C.  Area of a polygon.

D.  Shortest path between two points.

Q35. What is the running time of Chan’s algorithm?.

A.  O(log n).

B.  O(n log n).

C.  O(n log h).

D.  O(log h).

Q36. Who formulated Chan’s algorithm?.

A.  Timothy.

B.  Kirkpatrick.

C.  Frank Nielsen.

D.  Seidel.

Q37. The running time of Chan’s algorithm is obtained from combining two algorithms..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q38. Which of the following is called the “ultimate planar convex hull algorithm”?.

A.  Chan’s algorithm.

B.  Kirkpatrick-Seidel algorithm.

D.  Jarvis algorithm.

Q39. Which of the following algorithms is the simplest?.

A.  Chan’s algorithm.

B.  Kirkpatrick-Seidel algorithm.

D.  Jarvis algorithm.

Q40. What is the running time of Hershberger algorithm?.

A.  O(log n).

B.  O(n log n).

C.  O(n log h).

D.  O(log h).

Q41. Which of the following statements is not a part of Chan’s algorithm?.

A.  eliminate points not in the hull.

B.  recompute convex hull from scratch.

C.  merge previously calculated convex hull.

D.  reuse convex hull from the previous iteration.

Answer=  recompute convex hull from scratch

Q42. Which of the following factors account more to the cost of Chan’s algorithm?.

A.  computing a single convex hull.

B.  locating points that constitute a hull.

C.  computing convex hull in groups.

D.  merging convex hulls.

Answer=  computing convex hull in groups

Q43. Depth First Search is equivalent to which of the traversal in the Binary Trees?.

A.  Pre-order Traversal.

B.  Post-order Traversal.

C.  Level-order Traversal.

D.  In-order Traversal.