Q1: What is the time complexity of the convex hull algorithm using Graham’s scan?
(A) O(n log n)
(B) O(n²)
(C) O(n)
(D) O(n³)
Answer: (A) O(n log n)
Q2: Which of the following is a key characteristic of a Voronoi diagram?
(A) Divides a plane into regions based on proximity to a set of points
(B) Represents a triangulation of the points
(C) Identifies the convex hull of a set of points
(D) Measures the area of each region
Answer: (A) Divides a plane into regions based on proximity to a set of points
Q3: In a Delaunay triangulation, what is the condition for no points to lie inside the circumcircle of any triangle?
(A) The triangles must be equilateral
(B) The points must form a convex polygon
(C) There must be no obtuse triangles
(D) The triangulation must be maximally empty
Answer: (D) The triangulation must be maximally empty
Q4: What is the primary advantage of using the plane sweep algorithm in computational geometry?
(A) It guarantees an optimal solution in constant time
(B) It reduces the dimensionality of the problem
(C) It allows solving problems involving intersection of line segments efficiently
(D) It avoids the use of sorting algorithms
Answer: (C) It allows solving problems involving intersection of line segments efficiently
Q5: Which of the following is true about the Quickhull algorithm for computing the convex hull?
(A) It is guaranteed to run in O(n log n) time
(B) It works by recursively finding extreme points of a set
(C) It only works for 2-dimensional data
(D) It is not suitable for large data sets due to high space complexity
Answer: (B) It works by recursively finding extreme points of a set
Q6: What is the main purpose of a segment tree in computational geometry?
(A) To store the convex hull of a set of points
(B) To efficiently query geometric properties like intersections and range queries
(C) To calculate the Delaunay triangulation
(D) To represent the Voronoi diagram
Answer: (B) To efficiently query geometric properties like intersections and range queries
Q7: Which method is commonly used for finding the closest pair of points in a set of points?
(A) Convex hull algorithm
(B) Plane sweep algorithm
(C) Divide and conquer approach
(D) Nearest neighbor search
Answer: (C) Divide and conquer approach
Q8: Which of the following is an application of computational geometry in computer graphics?
(A) Pathfinding algorithms
(B) Collision detection
(C) Image processing
(D) All of the above
Answer: (D) All of the above
Q9: In the context of computational geometry, what does the term “robustness” typically refer to?
(A) The efficiency of the algorithm
(B) The algorithm’s ability to handle degenerate cases, such as collinear or coincident points
(C) The algorithm’s ability to compute large data sets
(D) The ability to visualize geometric objects
Answer: (B) The algorithm’s ability to handle degenerate cases, such as collinear or coincident points
Q10: Which of the following is the key challenge in computing Voronoi diagrams in higher dimensions?
(A) Increased computational time due to more complex geometric properties
(B) Difficulty in computing the convex hull
(C) Lack of efficient algorithms in higher dimensions
(D) Difficulty in visualizing the Voronoi regions
Answer: (A) Increased computational time due to more complex geometric properties