DSA Notes
Master computational geometry concepts, geometric algorithms, and problem-solving techniques.
What is Computational Geometry?
Computational geometry is the branch of computer science that studies algorithms for solving geometric problems. These problems involve points, lines, polygons, and other shapes in two-dimensional and three-dimensional space. If you have ever wondered how GPS navigation finds routes, how games detect collisions between objects, or how robotics systems plan movement paths — computational geometry is the answer.
Think of it this way: regular algorithms work with numbers and strings. Computational geometry algorithms work with coordinates, distances, angles, and shapes. The challenge is that geometric problems often have edge cases involving collinear points, overlapping shapes, and floating-point precision issues that make them trickier than they first appear.
Convex Hull — The Classic Problem
The convex hull is like stretching a rubber band around a set of nails on a board. It finds the smallest convex polygon that contains all given points.
Graham Scan Algorithm (O(n log n))
Time Complexity: O(n log n) due to sorting. The scan itself is O(n). Space Complexity: O(n) for storing the hull.
Line Segment Intersection
Determining whether two line segments intersect is fundamental to collision detection, map rendering, and circuit design:
def segments_intersect(p1, p2, p3, p4):
"""Check if segment p1-p2 intersects segment p3-p4"""
d1 = cross_product(p3, p4, p1)
d2 = cross_product(p3, p4, p2)
d3 = cross_product(p1, p2, p3)
d4 = cross_product(p1, p2, p4)
if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and \
((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
return True
# Check collinear cases
if d1 == 0 and on_segment(p3, p4, p1): return True
if d2 == 0 and on_segment(p3, p4, p2): return True
if d3 == 0 and on_segment(p1, p2, p3): return True
if d4 == 0 and on_segment(p1, p2, p4): return True
return False
def on_segment(p, q, r):
"""Check if point r lies on segment p-q"""
return (min(p.x, q.x) <= r.x <= max(p.x, q.x) and
min(p.y, q.y) <= r.y <= max(p.y, q.y))Closest Pair of Points
Finding the two closest points among n points. The naive approach checks all pairs (O(n²)), but the divide and conquer algorithm achieves O(n log n):
Algorithm idea:
- Sort points by x-coordinate
- Divide into left and right halves
- Recursively find closest pair in each half
- Check pairs that cross the dividing line (strip region)
- Return minimum of all three distances
Polygon Area (Shoelace Formula)
Calculate the area of any polygon given its vertices:
Complexity Analysis
| Algorithm | Time | Space | Use Case |
|---|---|---|---|
| Convex Hull (Graham Scan) | O(n log n) | O(n) | Enclosing boundary |
| Line Segment Intersection | O(1) | O(1) | Collision detection |
| Closest Pair (Divide & Conquer) | O(n log n) | O(n) | Proximity queries |
| Point in Polygon (Ray Casting) | O(n) | O(1) | Location queries |
| Polygon Area (Shoelace) | O(n) | O(1) | Area measurement |
| Sweep Line (All Intersections) | O((n+k) log n) | O(n) | k intersections found |
Real-World Applications
- Computer graphics and gaming — collision detection, rendering, shadow casting
- GIS and mapping — polygon overlay, point-in-region queries, route planning
- Robotics — path planning, obstacle avoidance, workspace analysis
- CAD/CAM — shape design, manufacturing tolerance, mesh generation
- Network design — minimum spanning trees on geographic data, facility location
- Image processing — shape recognition, boundary detection, image segmentation
Interview Questions
Q1: How do you determine if a point is inside a polygon? A: Use the Ray Casting algorithm — cast a ray from the point in any direction and count how many times it crosses the polygon boundary. Odd crossings = inside, even crossings = outside.
Q2: What is the time complexity of finding the convex hull? A: O(n log n) for algorithms like Graham Scan and Andrew's Monotone Chain. The sorting step dominates. Theoretically, O(n log h) is achievable with output-sensitive algorithms where h is the hull size.
Q3: How do you handle floating-point precision issues? A: Use epsilon comparisons instead of exact equality. For competitive programming, use integer coordinates and avoid division. In production, use robust geometric predicates or exact arithmetic libraries.
Q4: What is the Sweep Line technique? A: A vertical line sweeps from left to right across the plane. Events (point encounters, segment starts/ends) are processed in order. Active segments are maintained in a balanced BST. This technique solves many geometric problems efficiently.
Q5: How do you find all intersections among n line segments? A: The Bentley-Ottmann sweep line algorithm finds all k intersections in O((n+k) log n) time, compared to O(n²) for checking all pairs.
Key Takeaways
- The cross product is your most important tool — it determines orientation and drives most algorithms
- Convex hull is the most commonly asked computational geometry problem in interviews
- Edge cases (collinear points, overlapping segments) make geometric algorithms tricky
- Floating-point precision requires careful handling in production code
- Most practical problems reduce to a small set of fundamental operations: point location, intersection testing, and hull computation
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Computational Geometry - Algorithms and Techniques.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, advanced, topics, computational
Related Data Structures & Algorithms Topics