Computational Geometry Topics

All algorithms are implemented in C++. OpenGL is used for graphical representation.

Computation of Convex Hull

The problem description is available here

Time Complexity of Graham Scan Algorithm:

Time complexity of Graham Scan algorithm is always O(nlogn) irrespective of the input. O(nlogn) time is needed while sorting the vertices according to their angle with the most bottom-right vertex.

1. Graham Scan performs better than Gift Wrapping	2. Graham Scan performs worse than Gift Wrapping
Complexity Graham Scan: O(nlogn) Gift Wrapping: O(n^2)	Complexity Graham Scan: O(nlogn) Gift Wrapping: O(nh); here h=4

3. Graham Scan performs better than Quick Hull	4. Graham Scan performs same as Quick Hull
Complexity Graham Scan: O(nlogn) Quick Hull: O(n^2)	Complexity Graham Scan: O(nlogn) Quick Hull: O(nlogn)

Polygon Partitioning

The problem description is available here

Data Structure Used: To store the vertices, I used structure with the following attributes:

• X coordinate, Y coordinate
• Sequence of input
• Vertex type
• Index of the helper vertex

To store the edges, only the starting point is used. As the input is scanned in counter clockwise direction, so the other vertex of the edge must be the next point in input.

A set is maintained to store the edges in T. The < Operator was overloaded to maintain the ordering in the set. To find an edge immediately left of a vertex, the index in which this vertex would be inserted was calculated. The edge of the previous index is the immediate left edge.

Input polygon	Y-monotone pieces
Polygon triangulation	Another example

Delaunay Triangulation & Voronoi Diagram

The problem description is available here

Input points	Delaunay Triangulation
Voronoi Diagram	Another example