Lab 08 — Advanced Geometry

A: 1 ≤ N ≤ 10^5. Coordinates fit in int32.
B: 1 ≤ N ≤ 10^5. Up to K = O(N²) intersections in pathological cases; for the algorithm to be efficient, K << N².

Clarifying Questions

Should collinear hull points be included or skipped?
Are duplicates possible?

Should overlapping segments count as one intersection or many?
Touching at endpoints?

Examples

A

Points: [(0,0), (1,1), (2,0), (1,-1)]
Hull: [(0,0), (2,0), (1,1)] (counterclockwise; (1,-1) is below)
Wait — (1,-1) is also on the hull. Correct hull: [(0,0), (1,-1), (2,0), (1,1)].

B

Segments: [((0,0),(4,4)), ((0,4),(4,0))]
Intersect at (2,2). Answer: 1.

Brute Force

A: gift-wrapping (Jarvis march) — O(N · H) where H = hull size. Worst case O(N²). B: check every pair — O(N²).

Brute Force Complexity

A: O(NH) worst-case O(N²)
B: O(N²)

For N = 10^5: 10^10 — TLE.

Optimization Path

A — Andrew’s Monotone Chain

Sort points lexicographically by (x, y).
Build upper hull: iterate left to right; pop top of hull while it makes a non-right turn.
Build lower hull: iterate right to left; pop while non-right turn.
Concatenate (excluding shared endpoints).

def cross(O, A, B):
    return (A[0]-O[0]) * (B[1]-O[1]) - (A[1]-O[1]) * (B[0]-O[0])

def convex_hull(points):
    points = sorted(set(points))
    if len(points) <= 1: return points
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

B — Bentley-Ottmann Sweep Line

Event queue: segment endpoints + computed intersections, ordered by x.
Status: balanced BST of active segments, ordered by y at the sweep line.
At a “left endpoint” event: insert into status; check intersection with neighbors above/below.
At a “right endpoint” event: remove from status; check intersection between the new neighbors.
At an “intersection” event: swap the two segments in status; check intersections with new neighbors.

O((N + K) log N) where K = number of intersections.

Final Expected Approach

Convex hull: as above.

Bentley-Ottmann: full implementation is 200+ lines with all edge cases. For most interviews, even discussing the structure is enough — full code is unlikely to be required.

Data Structures

A: sorted list, stack-like list for hull construction
B: priority queue (event queue), balanced BST or sorted list with O(log N) ops (status)

Correctness Argument

A

Sorting by x (then y) ensures we visit points in a consistent order.
“Right turn” (cross product > 0) means we’re making a convex angle; popping ensures we never include a concave point.
Lower and upper hulls cover all hull vertices; concatenation gives full hull in CCW order.

B

Two segments can only intersect when they are adjacent in the y-order at some x.
The sweep maintains adjacency; new adjacencies arise at endpoints and intersections.
Each intersection is detected exactly once (at the moment the segments become adjacent).

Complexity

A: O(N log N) for sort + O(N) for chain construction.
B: O((N + K) log N).

Implementation Requirements

Use integer arithmetic for cross product when possible (avoids floating-point errors)
Handle collinear hull points consistently (include or exclude as required)
For segment intersection: distinguish proper intersection (interior) from touching (endpoint)
Watch for vertical segments (event ordering edge case)

Tests

A

Single point → [point]
Two points → [both]
Three collinear points → [endpoints only] (or all three, depending on convention)
Square (4 corners + 5 interior) → 4 corners
All points on a circle → all on hull
Many duplicates

B

No intersections (parallel lines)
All intersect at one point (n lines through origin)
Random N = 100 vs O(N²) brute force

Follow-up Questions

Convex hull in 3D. → Quickhull or gift wrapping in 3D; O(N²) worst.
Dynamic convex hull (online insertions). → Overmars-van Leeuwen; O(log² N) per update.
Compute area of hull. → Shoelace formula.
Diameter of hull (farthest pair). → Rotating calipers, O(N).

Report intersections, not just count. → Same structure; collect points.
Line-line intersection in projective coords. → Avoids special-casing parallels.
Segments may overlap. → More complex event handling.
Robust orientation predicate. → Adaptive precision; Shewchuk’s predicates.

Product Extension

Mapping: route simplification (Ramer-Douglas-Peucker)
Games: collision detection (broad phase uses sweep)
CAD: boolean operations on polygons (sweep-based)
Robotics: configuration space construction

Language/Runtime Follow-ups

C++: geometry libraries (CGAL) are massive and correct but complex.
Python: Shapely for production; for interview, implement primitives.
Java: java.awt.geom.* has some primitives.

Common Bugs

Floating-point comparison without epsilon: false negatives on coincident points.
cross < 0 vs cross <= 0: different hull conventions (collinear in or out).
Forgot to dedupe input points before convex hull.
Sweep-line: vertical segments treated incorrectly. Add small perturbation or special-case.
Sweep-line: intersection on the sweep line not detected because status ordering is computed at the wrong x.

Debugging Strategy

Plot the points and hull (matplotlib or similar)
For small cases, enumerate hull by hand and verify
For sweep-line: log every event and the status before/after

Mastery Criteria

Implement Andrew’s monotone chain in ≤ 30 min from memory
Implement basic segment-intersection check in ≤ 15 min
Understand the Bentley-Ottmann structure (even without writing 200 lines)
Apply rotating calipers for hull diameter
Recognize when integer arithmetic suffices vs when floating-point is unavoidable
State complexity precisely

LeetCode Interview — Extreme Coding