Computational Geometry MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: November 25, 2024

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