ICS215 Data Structures II
Module 1
Presented by
Dr. Dhakshayani J
Assistant Professor
IIIT Kottayam
Computational Geometry
Computational geometry is an area of mathematics in which we perform
calculations related to geometric objects, such as points, lines, polygons.
• Input: Set of geometric objects, such as a set of points, a set of line
segments, or the vertices of the polygon in counterclockwise order.
• Output: Object such as whether any of the lines intersect, or perhaps a
new geometric object, such as the convex hull (smallest enclosing
convex polygon) of the set of points.
Geometric Algorithms
• Geometric algorithms solve problems in computational
geometry
Problems on Geometric algorithms
1. Klee’s Algorithm
Line 2. Manhattan distance problems
3. Collinear checking
4. Identifying Integral points inside a Triangle
Triang 5. Circumcenter of a Triangle
le 6. Triangular Matchstick Number
7. area of Circumcircle of an Equilateral Triangle
8. Number of rectangles in N*M grid
Rectang 9. Area of two overlapping rectangles
le
10. Number of unique rectangles formed using N unit squares
Circl 11. Circle and Lattice Points
e 12. Pizza cut problem
1. Klee’s
Algorithm
Klee's Algorithm- Length Of Union Of Segments of a line
Problem statement:
Given starting and ending positions of segments on a line, the task is to
take the union of all given segments and find length covered by these
segments.
2 5 9 12
4 8
2 12
Example 1
• If two same co-ordinates,
The left co-ordinate will have higher priority,
(5,f) > (5,t) 5
2
5 8
Pseudocode for Klee's Algorithm
• Input:
• A list of segments, each defined by a pair of integers representing the
start and end points.
• Initialize:
1. An empty list points to store starting and ending points of segments.
2. A variable result to store the total union length, initialized to 0.
3. A counter to track the number of overlapping segments, initialized
to 0.
• Populate Points:
For each segment:
1. Add a point representing the start (with a marker indicating it's a
start).
2. Add a point representing the end (with a marker indicating it's an
end).
• Sort Points:
• Sort the list points based on the position of the points.
• In case of a tie, give preference to end points over start points.
Pseudocode for Klee's Algorithm
• Calculate Union Length:
• Traverse through the sorted list of points:
• If Counter is greater than 0, add the difference between the current
point and the previous point to result.
• If the current point is a start, increment Counter.
• If the current point is an end, decrement Counter.
• Output:
• Return result as the total length covered by the union of segments.
Example 2
2 6 7 10
5 8
• Time complexity - ?
• Modified version:
Find the maximum length of a continuous union of line segments
