Q.1 What is the primary purpose of the Convex Hull in computational geometry?
To find the smallest circle enclosing a set of points
To find the largest area polygon inside a set of points
To find the smallest convex polygon enclosing all points
To sort points based on their coordinates
Explanation - The convex hull is the smallest convex polygon that contains all the points in a given set.
Correct answer is: To find the smallest convex polygon enclosing all points
Q.2 Which algorithm is commonly used for computing the convex hull in 2D?
Dijkstra's Algorithm
Graham's Scan
Kruskal's Algorithm
Prim's Algorithm
Explanation - Graham's Scan is a well-known algorithm for computing the convex hull of a set of points in 2D space efficiently.
Correct answer is: Graham's Scan
Q.3 What is the time complexity of the Jarvis March (Gift Wrapping) algorithm for convex hull?
O(n log n)
O(n^2)
O(n)
O(log n)
Explanation - Jarvis March runs in O(nh) time, where n is the number of points and h is the number of points on the hull. In the worst case, h = n, giving O(n^2).
Correct answer is: O(n^2)
Q.4 Which data structure is often used in Sweep Line algorithms for computational geometry?
Queue
Stack
Balanced Binary Search Tree
Hash Table
Explanation - Sweep line algorithms maintain a dynamic set of line segments intersecting the sweep line, often using a balanced BST for efficient insertion, deletion, and neighbor queries.
Correct answer is: Balanced Binary Search Tree
Q.5 What does the Rotating Calipers technique compute?
Convex hull
Closest pair of points
Diameter and width of convex polygons
Voronoi diagram
Explanation - Rotating calipers is a technique used to compute geometric properties like diameter, width, or minimal bounding rectangles of convex polygons efficiently.
Correct answer is: Diameter and width of convex polygons
Q.6 In computational geometry, what is a Voronoi diagram used for?
Partitioning space based on distance to points
Sorting points by coordinates
Finding the convex hull
Computing graph shortest paths
Explanation - A Voronoi diagram partitions a plane into regions such that each region contains all points closest to a specific site point.
Correct answer is: Partitioning space based on distance to points
Q.7 Which algorithm is typically used to compute Delaunay triangulation?
Divide and Conquer
Floyd-Warshall
Prim's Algorithm
Bellman-Ford
Explanation - Divide and Conquer is a common approach to compute Delaunay triangulations efficiently in 2D space.
Correct answer is: Divide and Conquer
Q.8 What is the dual graph of a Voronoi diagram called?
Convex hull
Delaunay triangulation
Minimum spanning tree
Sweep line
Explanation - The Delaunay triangulation is the dual of the Voronoi diagram, connecting points whose Voronoi cells share an edge.
Correct answer is: Delaunay triangulation
Q.9 Which problem is solved by the Line Segment Intersection algorithm?
Finding convex hull
Finding all intersecting pairs of line segments
Sorting points by distance
Constructing a Voronoi diagram
Explanation - The Line Segment Intersection problem identifies all pairs of segments in a set that intersect each other, often solved using a sweep line technique.
Correct answer is: Finding all intersecting pairs of line segments
Q.10 What is the primary advantage of using a KD-Tree in computational geometry?
Faster sorting of points
Efficient nearest neighbor queries
Computing convex hull
Finding intersections of line segments
Explanation - KD-Trees partition k-dimensional space to allow fast nearest neighbor searches and range queries.
Correct answer is: Efficient nearest neighbor queries
Q.11 Which algorithm finds the closest pair of points in 2D space efficiently?
Brute force comparison
Divide and Conquer
Floyd-Warshall
Kruskal's Algorithm
Explanation - The Divide and Conquer algorithm finds the closest pair of points in O(n log n) time, better than the brute force O(n^2) approach.
Correct answer is: Divide and Conquer
Q.12 In 2D geometry, how many points are needed at minimum to form a non-degenerate convex hull?
1
2
3
4
Explanation - At least three non-collinear points are needed to form a non-degenerate convex polygon (triangle) in 2D space.
Correct answer is: 3
Q.13 Which computational geometry structure helps in efficiently answering range queries?
Stack
KD-Tree
Queue
Hash Map
Explanation - KD-Trees allow efficient range queries by recursively partitioning space along coordinate axes.
Correct answer is: KD-Tree
Q.14 What is the purpose of the Sweep Line algorithm in computational geometry?
To sort points by coordinates
To process geometric events in order along a line
To find the convex hull
To compute Delaunay triangulation
Explanation - Sweep Line algorithms process events in a specific order (usually sorted by x-coordinate), maintaining an active set to solve problems like segment intersections.
Correct answer is: To process geometric events in order along a line
Q.15 In computational geometry, the term 'polygon triangulation' refers to:
Finding the convex hull
Dividing a polygon into triangles without adding vertices
Computing the Voronoi diagram
Finding the shortest path inside the polygon
Explanation - Polygon triangulation splits a polygon into non-overlapping triangles using existing vertices, which is useful in graphics and geometry processing.
Correct answer is: Dividing a polygon into triangles without adding vertices
Q.16 What is the expected time complexity of randomized incremental convex hull algorithms?
O(n log n)
O(n^2)
O(n)
O(log n)
Explanation - Randomized incremental algorithms for convex hull construction typically run in expected O(n log n) time in 2D.
Correct answer is: O(n log n)
Q.17 Which of the following problems is NOT commonly addressed by computational geometry?
Convex hull
Shortest path in weighted graphs
Voronoi diagram
Line segment intersection
Explanation - Shortest path in weighted graphs is primarily a graph algorithm problem, not geometric computation.
Correct answer is: Shortest path in weighted graphs
Q.18 What is the worst-case time complexity of computing a Voronoi diagram for n points using Fortune’s algorithm?
O(n^2)
O(n log n)
O(n)
O(log n)
Explanation - Fortune’s sweep line algorithm constructs the Voronoi diagram in O(n log n) time.
Correct answer is: O(n log n)
Q.19 Which geometric structure is used to represent all points equidistant from two or more given points?
Convex hull
Voronoi edge
KD-Tree
Sweep line
Explanation - A Voronoi edge is the locus of points equidistant to two neighboring sites in a Voronoi diagram.
Correct answer is: Voronoi edge
Q.20 What type of geometric problem is 'point location'?
Finding convex hull
Determining which region contains a given point
Sorting points
Computing triangulation
Explanation - Point location determines the specific subdivision or polygon in which a query point lies.
Correct answer is: Determining which region contains a given point
Q.21 Which approach is commonly used for 3D convex hull construction?
Graham's Scan
Incremental Algorithm
Dijkstra's Algorithm
Floyd-Warshall Algorithm
Explanation - The incremental algorithm adds points one by one to a 3D convex hull, updating faces efficiently.
Correct answer is: Incremental Algorithm
Q.22 In computational geometry, 'half-plane intersection' is used to:
Compute convex polygons
Sort points by y-coordinate
Compute line segment intersections
Build KD-Trees
Explanation - Half-plane intersection finds the intersection of multiple half-planes, resulting in a convex polygon if the intersection is non-empty.
Correct answer is: Compute convex polygons
Q.23 What is a key property of a Delaunay triangulation?
It maximizes the minimum angle of triangles
It minimizes the perimeter of triangles
It sorts points by distance
It computes nearest neighbors only
Explanation - Delaunay triangulations maximize the minimum angle among all triangles, avoiding skinny triangles and producing well-shaped triangles.
Correct answer is: It maximizes the minimum angle of triangles
Q.24 Which algorithm is used to find all intersections in a set of line segments efficiently?
Sweep Line Algorithm
Graham's Scan
Divide and Conquer
Prim's Algorithm
Explanation - The sweep line algorithm efficiently finds all intersections among line segments by maintaining an active set and event queue.
Correct answer is: Sweep Line Algorithm
Q.25 What is the main application of the Minkowski sum in computational geometry?
Path planning and collision detection
Computing convex hull
Voronoi diagram construction
Polygon triangulation
Explanation - Minkowski sum is used to combine shapes, commonly applied in robotics for path planning and collision detection between polygons.
Correct answer is: Path planning and collision detection