20 Geometric Algorithms Quiz Questions and Answers

1. Question: What is the primary purpose of the Convex Hull algorithm in computational geometry?
A. To find the shortest path between points
B. To enclose a set of points with the smallest convex polygon
C. To calculate the area of a polygon
D. To determine if points are collinear
Answer: B
Explanation: The Convex Hull algorithm creates the smallest convex polygon that contains all the points, similar to wrapping a rubber band around them, which is essential for shape simplification and collision detection.

2. Question: Which algorithm is commonly used to compute the Convex Hull of a set of points?
A. Dijkstra’s algorithm
B. Graham’s scan
C. QuickSort
D. Binary Search
Answer: B
Explanation: Graham’s scan sorts the points and builds the hull by ensuring a counterclockwise order, making it efficient with a time complexity of O(n log n).

3. Question: In the Jarvis March algorithm for Convex Hull, what is the initial step?
A. Sort the points by x-coordinate
B. Find the point with the lowest y-coordinate
C. Compute the centroid of all points
D. Check for collinear points
Answer: B
Explanation: Jarvis March starts by selecting the point with the lowest y-coordinate (and lowest x-coordinate in case of ties) as the starting point for the gift-wrapping process.

4. Question: What is the time complexity of the Andrew’s algorithm for Convex Hull?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
Answer: B
Explanation: Andrew’s algorithm, a variation of Graham’s scan, sorts points by x-coordinate and then builds the upper and lower hulls, resulting in O(n log n) time due to the sorting step.

5. Question: How does the Line Segment Intersection algorithm determine if two line segments intersect?
A. By checking if endpoints are collinear
B. By using the cross product to see if endpoints straddle each other
C. By calculating the midpoint of both segments
D. By computing the distance between segments
Answer: B
Explanation: The algorithm uses the orientation (cross product) of points to check if the endpoints of one segment lie on opposite sides of the other, confirming an intersection.

6. Question: In the Bentley-Ottmann algorithm, what data structure is primarily used for detecting line segment intersections?
A. Binary Search Tree
B. Sweep Line Status (e.g., balanced binary search tree)
C. Hash Table
D. Queue
Answer: B
Explanation: The Bentley-Ottmann algorithm employs a sweep line and maintains an event queue and a status structure (like a balanced BST) to track active line segments efficiently.

7. Question: What is the output of the Closest Pair of Points algorithm?
A. The convex hull of the points
B. The pair of points with the minimum distance
C. All intersecting lines
D. The Voronoi diagram
Answer: B
Explanation: This divide-and-conquer algorithm finds the two closest points in a set, with a time complexity of O(n log n), by recursively dividing the plane and checking minimum distances.

8. Question: Which method is used in the Divide and Conquer approach for the Closest Pair algorithm?
A. Sorting points by angle
B. Splitting the set into halves and finding minimum distances
C. Checking all pairs brute force
D. Using a sweep line
Answer: B
Explanation: The algorithm divides the point set into two halves, solves recursively, and then checks the strip around the dividing line for closer pairs.

9. Question: In Voronoi Diagram construction, what does each cell represent?
A. The area closer to a specific site than to any other
B. The intersection points of lines
C. The convex hull boundary
D. The shortest path between sites
Answer: A
Explanation: A Voronoi Diagram partitions the plane into regions where each region consists of points closer to its associated site than to any other site.

10. Question: What is the time complexity of building a Voronoi Diagram using Fortune’s algorithm?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
Answer: B
Explanation: Fortune’s algorithm uses a sweep line approach, maintaining a beach line data structure, resulting in O(n log n) time for n sites.

11. Question: How does the Point-in-Polygon algorithm using the Ray Casting method work?
A. By checking the angle from the point to polygon vertices
B. By drawing a ray from the point and counting edge intersections
C. By computing the centroid of the polygon
D. By verifying if the point is on an edge
Answer: B
Explanation: The Ray Casting algorithm casts a ray from the point to infinity and counts how many edges it intersects; an odd count means the point is inside.

12. Question: In Polygon Triangulation, what is the role of the Ear Clipping algorithm?
A. To find the area of the polygon
B. To divide a simple polygon into triangles by removing “ears”
C. To check for concavity
D. To compute the convex hull
Answer: B
Explanation: Ear Clipping identifies and removes triangular “ears” from a polygon, recursively triangulating it with O(n) time after initial checks.

13. Question: What does the Rotating Calipers technique primarily compute?
A. The diameter of a set of points
B. Intersections of lines
C. The area of a polygon
D. Shortest paths
Answer: A
Explanation: Rotating Calipers is used to find the width, diameter, or other extremal distances of a convex hull by “rotating” parallel lines around the shape.

14. Question: In the context of geometric algorithms, what is a Delaunay Triangulation?
A. A triangulation where no point is inside the circumcircle of any triangle
B. A simple division of points into triangles
C. The convex hull of points
D. A Voronoi diagram
Answer: A
Explanation: Delaunay Triangulation ensures that the circumcircle of each triangle contains no other points, maximizing the minimum angle and avoiding skinny triangles.

15. Question: Which algorithm is used for computing the intersection of two convex polygons?
A. Graham’s scan
B. Separating Axis Theorem
C. Jarvis March
D. Ray Casting
Answer: B
Explanation: The Separating Axis Theorem checks for overlaps by projecting polygons onto axes; if no separating axis exists, the polygons intersect.

16. Question: What is the time complexity of the naive algorithm for Line Segment Intersection?
A. O(1)
B. O(n log n)
C. O(n^2)
D. O(log n)
Answer: C
Explanation: The naive approach checks every pair of segments, leading to O(n^2) time, which is inefficient for large sets.

17. Question: In the Sweep Line algorithm for rectangle union, what structure maintains the active segments?
A. A stack
B. A priority queue
C. A balanced binary search tree
D. A hash map
Answer: C
Explanation: A balanced binary search tree (e.g., in the status structure) keeps track of the order of intersecting or active segments as the sweep line moves.

18. Question: How does Chan’s algorithm for Convex Hull improve on previous methods?
A. It works in O(n) time for nearly sorted points
B. It uses a randomized approach
C. It outputs the Voronoi diagram
D. It is purely brute force
Answer: A
Explanation: Chan’s algorithm is an output-sensitive method that runs in O(n + h log h) time, where h is the number of hull points, making it efficient for small hulls.

19. Question: What is the purpose of the Art Gallery Theorem in geometric algorithms?
A. To find the minimum guards needed to cover a polygon
B. To compute polygon areas
C. To detect line intersections
D. To build Voronoi diagrams
Answer: A
Explanation: The Art Gallery Theorem determines that floor(n/3) guards are sufficient and sometimes necessary to cover a simple polygon with n vertices.

20. Question: In a KD-Tree for nearest neighbor search, how are points organized?
A. By angle from a fixed point
B. By alternating dimensions (e.g., x then y)
C. Randomly for quick access
D. By distance from the origin
Answer: B
Explanation: A KD-Tree partitions the space by splitting along the median of alternating dimensions, enabling efficient nearest neighbor queries in O(log n) average time.