THEORY EXAMINATION (SEM–VI) 2016-17 COMPUTATIONAL GEOMETRY

COMPUTATIONAL GEOMETRY – NCS061

B.Tech (SEM VI) | Section-wise Solved Answers

SECTION – A

(Explain the following – 2 marks each)

(a) Fortune’s Sweep

Fortune’s sweep is an efficient plane sweep algorithm used to construct Voronoi diagrams in O(n log n) time. It moves a sweep line across the plane while maintaining a beach line structure.

(b) Minimum Spanning Tree

A minimum spanning tree (MST) connects all vertices of a weighted graph with minimum total edge weight and without forming cycles. In computational geometry, MSTs are used in clustering and proximity problems.

(c) Separating Chains

Separating chains are polygonal chains used to divide planar point sets or regions. They help determine separability between geometric objects.

(d) Reflections

Reflection is a geometric transformation that produces a mirror image of an object across a line or plane. It is commonly used in symmetry analysis and geometric modeling.

(e) Perspective Projection

Perspective projection maps 3D points onto a 2D plane, simulating human vision. Objects farther from the viewer appear smaller, giving depth perception.

(f) Delaunay Triangulations

Delaunay triangulation maximizes the minimum angle of triangles and avoids skinny triangles. It is widely used in mesh generation and interpolation.

(g) Quick Hull

Quick Hull is a divide-and-conquer algorithm used to compute the convex hull of a set of points. It works similarly to Quick Sort.

(h) Planar Graphs

A planar graph can be drawn on a plane such that no two edges cross each other. Planar graphs are fundamental in geometric graph algorithms.

(i) Interval Trees

Interval trees are data structures used to efficiently store intervals and answer queries such as finding all intervals that overlap a given interval.

(j) Segment Trees

Segment trees are hierarchical data structures used for range searching and querying intervals in logarithmic time.

SECTION – B

(Attempt any five – explained clearly)

(a) Convex Hull: Orientation and Limitation

A convex hull is the smallest convex polygon enclosing all points in a given set. Orientation tests (clockwise or counter-clockwise) help determine hull edges. Limitations include sensitivity to collinear points and higher computational cost in higher dimensions.

(b) Triangulation

Triangulation divides a polygon or point set into triangles.

Angular triangulation focuses on minimizing angles, while
Point-set triangulation connects given points without overlap, covering the convex hull.

(c) Divide and Conquer, Flip and Incremental Algorithms

Divide and conquer breaks a problem into smaller subproblems.
Flip algorithms improve triangulation quality by edge flipping.
Incremental algorithms insert points one by one and update structures dynamically.

(d) Visibility

Visibility determines whether two points can see each other without obstruction.

Weak visibility: Partial visibility exists.

Strong visibility: Entire object is visible.

Algorithms use ray casting and angular sweeps.

(e) Voronoi Diagrams

A Voronoi diagram partitions space into regions where each region contains points closest to one site. Properties include convex cells and perpendicular bisectors.

(f) Zone Theorem

The zone theorem states that the complexity of the zone of a line in an arrangement of n lines is O(n). It is useful in range searching and motion planning.

(g) Higher Dimensional Range Searching

It involves querying multidimensional data points within a specified range. Example: finding all points within a 3D box using KD-trees.

(h) Robust Geometric Computing

It ensures correctness despite numerical errors. Techniques include exact arithmetic and error bounds to avoid incorrect geometric decisions.

SECTION – C

(Attempt any two – long answers)

(3) Differentiation

Classical vs Computational Geometry
Classical geometry is theoretical, while computational geometry focuses on algorithmic problem-solving.

Plane vs 3D Line
Plane geometry deals with 2D objects, whereas 3D lines exist in three-dimensional space.

Convex vs Concave
Convex shapes have all interior angles < 180°, concave shapes have at least one angle > 180°.

(4) Sweep Techniques

Sweep techniques process geometric objects by moving a line across space.

Plane sweep for segment intersection detects intersecting line segments efficiently.

Topological sweep handles arrangements without requiring numeric sorting.

(5) Short Notes

Ham-Sandwich Cuts
A theorem stating that a single line can divide multiple sets equally.

Fractional Cascading
A technique that speeds up multiple related searches across data structures.

Concatenable Queues
Queues that support fast concatenation and splitting operations.