Chapter 33: Computational Geometry

Computational geometry is the branch of computer science that studies algorithms for solving geometric problems. Applications span computer graphics, robotics, VLSI design, CAD, molecular modeling, manufacturing, and statistics.

• Input: typically a description of geometric objects (points, line segments, polygon vertices)
• Output: a response to a query (e.g., do lines intersect?) or a new geometric object (e.g., convex hull)
• This chapter focuses on two-dimensional problems in the plane
• Points are represented as p = (x, y) where x, y ∈ ℝ
• An n-vertex polygon P is represented by a sequence ⟨p₀, p₁, ..., p_{n-1}⟩ of vertices in boundary order

---

33.1 Line-Segment Properties

Convex Combinations and Line Segments

• A convex combination of two distinct points p₁ = (x₁, y₁) and p₂ = (x₂, y₂) is any point p₃ = (x₃, y₃) such that for some α in [0, 1]:
  • x₃ = αx₁ + (1 − α)x₂
  • y₃ = αy₁ + (1 − α)y₂
  • Written as p₃ = αp₁ + (1 − α)p₂
• The line segment p₁p₂ is the set of all convex combinations of p₁ and p₂
• p₁ and p₂ are called the endpoints of the segment
• A directed segment p₀p₁ has a specified ordering; if p₀ is the origin (0,0), the directed segment can be treated as the vector p₁

Key Questions (all answerable in O(1) time)

1. Given two directed segments from a common endpoint p₀, is one clockwise from the other?
2. Given consecutive segments p₀p₁ and p₁p₂, do we make a left turn or right turn at p₁?
3. Do two line segments p₁p₂ and p₃p₄ intersect?

All methods use only additions, subtractions, multiplications, and comparisons — no division or trigonometric functions needed (avoids round-off error).

Cross Products

The cross product of vectors p₁ and p₂ is the signed area of the parallelogram formed by (0,0), p₁, p₂, and p₁ + p₂:

p₁ × p₂ = det | x₁  y₁ | = x₁y₂ − x₂y₁ = −(p₂ × p₁)
              | x₂  y₂ |

• If p₁ × p₂ > 0 → p₁ is clockwise from p₂ (relative to origin)
• If p₁ × p₂ < 0 → p₁ is counterclockwise from p₂
• If p₁ × p₂ = 0 → vectors are colinear (same or opposite directions)

To determine orientation of directed segment p₀p₁ relative to p₀p₂ with common endpoint p₀, translate to use p₀ as origin and compute:

(p₁ − p₀) × (p₂ − p₀) = (x₁ − x₀)(y₂ − y₀) − (x₂ − x₀)(y₁ − y₀)

• Positive → p₀p₁ is clockwise from p₀p₂
• Negative → p₀p₁ is counterclockwise from p₀p₂

Determining Left/Right Turns

Given consecutive segments p₀p₁ and p₁p₂, to determine the turn direction at p₁:

Compute the cross product:

(p₂ − p₀) × (p₁ − p₀)

• Negative → counterclockwise (p₀p₂ is CCW w.r.t. p₀p₁) → left turn at p₁
• Positive → clockwise → right turn at p₁
• Zero → points p₀, p₁, p₂ are colinear

Determining Whether Two Line Segments Intersect

Two segments intersect if and only if either (or both):

1. Each segment straddles the line containing the other (endpoints lie on opposite sides)
2. An endpoint of one segment lies on the other segment (boundary case)

SEGMENTS-INTERSECT(p₁, p₂, p₃, p₄)
  d₁ = DIRECTION(p₃, p₄, p₁)
  d₂ = DIRECTION(p₃, p₄, p₂)
  d₃ = DIRECTION(p₁, p₂, p₃)
  d₄ = DIRECTION(p₁, p₂, p₄)
  if ((d₁ > 0 and d₂ < 0) or (d₁ < 0 and d₂ > 0)) and
     ((d₃ > 0 and d₄ < 0) or (d₃ < 0 and d₄ > 0))
      return TRUE
  elseif d₁ == 0 and ON-SEGMENT(p₃, p₄, p₁)
      return TRUE
  elseif d₂ == 0 and ON-SEGMENT(p₃, p₄, p₂)
      return TRUE
  elseif d₃ == 0 and ON-SEGMENT(p₁, p₂, p₃)
      return TRUE
  elseif d₄ == 0 and ON-SEGMENT(p₁, p₂, p₄)
      return TRUE
  else return FALSE

DIRECTION(pᵢ, pⱼ, pₖ)
  return (pₖ − pᵢ) × (pⱼ − pᵢ)

ON-SEGMENT(pᵢ, pⱼ, pₖ)
  if min(xᵢ, xⱼ) ≤ xₖ ≤ max(xᵢ, xⱼ) and
     min(yᵢ, yⱼ) ≤ yₖ ≤ max(yᵢ, yⱼ)
      return TRUE
  else return FALSE

How it works:

• Lines 1–4 compute relative orientation dₖ of each endpoint pₖ w.r.t. the other segment
• If signs of d₁ and d₂ differ AND signs of d₃ and d₄ differ → segments straddle each other → intersect
• If any dₖ = 0, then pₖ is colinear with the other segment; check if it lies between the endpoints using ON-SEGMENT
• ON-SEGMENT checks both x and y dimensions (both are necessary)

---

33.2 Determining Whether Any Pair of Segments Intersects

This section presents an O(n lg n) algorithm using the sweep line technique to determine whether any two segments in a set of n segments intersect. It determines only existence, not all intersections (finding all intersections takes Θ(n²) in the worst case).

The Sweep Line Technique

An imaginary vertical sweep line passes through the geometric objects from left to right. The x-dimension is treated as time.

Simplifying assumptions:

1. No input segment is vertical
2. No three input segments intersect at a single point

Ordering Segments

• Two segments are comparable at x if the vertical sweep line at x-coordinate x intersects both
• s₁ is above s₂ at x (written s₁ ≻ₓ s₂) if s₁'s intersection with the sweep line is higher than s₂'s
• The relation ≻ₓ is a total preorder for all segments intersecting the sweep line at x (transitive, total, reflexive)
• When two segments intersect, they reverse their order in the total preorder
• At the intersection point, the two segments must be consecutive in the total preorder for some sweep line

Sweep Line Data Structures

1. Sweep-line status (T): relationships among objects the sweep line currently intersects (maintained as a red-black tree)
2. Event-point schedule: segment endpoints sorted left to right by x-coordinate

Operations on T (each O(lg n) using red-black trees):

• INSERT(T, s) — insert segment s
• DELETE(T, s) — delete segment s
• ABOVE(T, s) — return segment immediately above s
• BELOW(T, s) — return segment immediately below s

Key comparisons in the red-black tree use cross products instead of explicit keys.

Event Point Ordering

• Each segment endpoint is an event point
• Sort by increasing x-coordinate
• Tie-breaking: left endpoints before right endpoints; among ties, lower y-coordinates first
• Lexicographic sort on (x, e, y) where e = 0 for left endpoint, e = 1 for right endpoint

Algorithm

ANY-SEGMENTS-INTERSECT(S)
  T = ∅
  sort the endpoints of the segments in S from left to right,
      breaking ties by putting left endpoints before right endpoints
      and breaking further ties by putting points with lower
      y-coordinates first
  for each point p in the sorted list of endpoints
      if p is the left endpoint of a segment s
          INSERT(T, s)
          if (ABOVE(T, s) exists and intersects s)
             or (BELOW(T, s) exists and intersects s)
              return TRUE
      if p is the right endpoint of a segment s
          if both ABOVE(T, s) and BELOW(T, s) exist
             and ABOVE(T, s) intersects BELOW(T, s)
              return TRUE
          DELETE(T, s)
  return FALSE

Correctness Argument

• The algorithm returns TRUE only when it finds an actual intersection → no false positives
• If an intersection exists, let p be the leftmost intersection point (lowest y to break ties), between segments a and b
• Since no intersections occur left of p, the total preorder T is correct at all points left of p
• Segments a and b must become consecutive in T at some event point q on or before p
• At q, the algorithm detects the intersection in one of two ways:
  1. One of a, b is inserted and the other is its neighbor → detected at insertion (lines 4–7)
  2. A segment between a and b is deleted, making them consecutive → detected at deletion (lines 8–11)

Running Time: O(n lg n)

• Sorting 2n endpoints: O(n lg n)
• For loop: at most 2n iterations, each O(lg n) for red-black tree operations
• Intersection tests: O(1) each using cross products
• Total: O(n lg n)

---

33.3 Finding the Convex Hull

The convex hull of a set Q of points, denoted CH(Q), is the smallest convex polygon P for which each point in Q is either on the boundary of P or in its interior. Intuitively: the shape formed by a tight rubber band surrounding all the points (imagined as nails on a board).

• Every vertex of CH(Q) is a point in Q
• We assume all points are unique and Q contains at least 3 non-colinear points
• Both algorithms below output vertices in counterclockwise order

Other Methods (Overview)

Graham's Scan

Maintains a stack S of candidate points. Each point is pushed exactly once; non-hull points are eventually popped. When done, S contains exactly the vertices of CH(Q) in counterclockwise order.

GRAHAM-SCAN(Q)
  let p₀ be the point in Q with the minimum y-coordinate,
      or the leftmost such point in case of a tie
  let ⟨p₁, p₂, ..., pₘ⟩ be the remaining points in Q,
      sorted by polar angle in counterclockwise order around p₀
      (if more than one point has the same angle, remove all but
       the one that is farthest from p₀)
  if m < 2
      return "convex hull is empty"
  else let S be an empty stack
  PUSH(p₀, S)
  PUSH(p₁, S)
  PUSH(p₂, S)
  for i = 3 to m
      while the angle formed by points NEXT-TO-TOP(S), TOP(S),
            and pᵢ makes a nonleft turn
          POP(S)
      PUSH(pᵢ, S)
  return S

Step-by-step:

1. Choose p₀ as the lowest point (leftmost if tied) — guaranteed to be a hull vertex
2. Sort remaining points by polar angle relative to p₀ (using cross products, not trig)
   • Remove duplicates at the same angle, keeping only the farthest from p₀
3. Initialize stack with p₀, p₁, p₂
4. For each subsequent point pᵢ:
   • While the top two stack points and pᵢ form a nonleft turn (right turn or colinear), pop the top
   • Push pᵢ
5. Return the stack (the hull vertices in CCW order)

Why nonleft turn (not just right turn)? To exclude straight angles — no vertex of a convex polygon should be a convex combination of other vertices.

Correctness (Theorem 33.1):

Loop invariant: At the start of each iteration for point pᵢ, stack S contains exactly the vertices of CH({p₀, p₁, ..., p_{i-1}}) in counterclockwise order.

• Initialization: S = {p₀, p₁, p₂} forms CH(Q₂) ✓
• Maintenance: When processing pᵢ, popped points are interior to triangles formed by remaining points, so they cannot be hull vertices. After pushing pᵢ, S = CH(Qᵢ) ✓
• Termination: i = m + 1, so S = CH(Qₘ) = CH(Q) ✓

Running Time: O(n lg n)

• Finding p₀: Θ(n)
• Sorting by polar angle: O(n lg n)
• Stack operations: each point pushed exactly once, popped at most once → O(n) total by aggregate analysis (at most m − 2 pops total)
• Overall: O(n lg n)

Jarvis's March (Gift Wrapping)

Computes the convex hull by simulating wrapping a taut piece of paper around the point set. Runs in O(nh) time where h is the number of hull vertices.

Algorithm:

1. Start with p₀ = lowest point (same as Graham's scan)
2. Right chain: From p₀, repeatedly find the point with the smallest polar angle w.r.t. the current point (ties broken by farthest distance). Continue until reaching the highest point pₖ.
3. Left chain: From pₖ, repeatedly find the point with the smallest polar angle w.r.t. the negative x-axis. Continue until returning to p₀.

Key properties:

• Each step selects the next hull vertex by finding the minimum polar angle among all n points → O(n) per hull vertex
• Polar angle comparisons use cross products (O(1) each)
• Total: h vertices × O(n) per vertex = O(nh)

When to prefer Jarvis's march over Graham's scan:

• When h = o(lg n), Jarvis's march is asymptotically faster
• For h = O(lg n), Jarvis gives O(n lg n) — same as Graham
• For large h (close to n), Graham's scan is better

---

33.4 Finding the Closest Pair of Points

Given a set Q of n ≥ 2 points, find the two points with the smallest Euclidean distance:

d(p₁, p₂) = √((x₁ − x₂)² + (y₁ − y₂)²)

Applications include traffic-control systems (detecting potential collisions).

• Brute force: check all C(n,2) = Θ(n²) pairs
• Divide-and-conquer achieves O(n lg n) via T(n) = 2T(n/2) + O(n)

The Divide-and-Conquer Algorithm

Each recursive call receives subset P ⊆ Q and arrays X (sorted by x-coordinate) and Y (sorted by y-coordinate).

Base case: If |P| ≤ 3, use brute force.

Divide:

• Find a vertical line l that bisects P into PL (⌈|P|/2⌉ points on/left of l) and PR (⌊|P|/2⌋ points on/right of l)
• Split X into XL, XR (sorted by x)
• Split Y into YL, YR (sorted by y)

Conquer:

• Recursively find closest pair in PL → distance δL
• Recursively find closest pair in PR → distance δR
• Let δ = min(δL, δR)

Combine:

• The closest pair is either within PL, within PR, or has one point in each
• A cross-pair closer than δ must have both points within a 2δ-wide vertical strip centered at l

1. Create array Y′ = points from Y within the 2δ-wide strip (still sorted by y)
2. For each point p in Y′, check only the next 7 points in Y′ for a closer pair; track the best distance δ′
3. If δ′ < δ, return the strip pair; otherwise return the recursive result

Why Only 7 Points Need Checking

• Any cross-pair closer than δ must lie within a δ × 2δ rectangle centered at line l
• The left δ × δ square can hold at most 4 points from PL (since all PL points are ≥ δ apart)
• The right δ × δ square can hold at most 4 points from PR
• Total: at most 8 points in the rectangle
• Therefore each point needs to check at most the 7 points following it in Y′

Implementation: Presorting for O(n lg n)

The critical insight: we cannot afford to sort within each recursive call (that would give T(n) = 2T(n/2) + O(n lg n) = O(n lg² n)).

Solution: Presort once, then split sorted arrays in linear time.

Splitting a sorted array into two sorted subarrays (reverse of merge):

let YL[1..Y.length] and YR[1..Y.length] be new arrays
YL.length = YR.length = 0
for i = 1 to Y.length
    if Y[i] ∈ PL
        YL.length = YL.length + 1
        YL[YL.length] = Y[i]
    else
        YR.length = YR.length + 1
        YR[YR.length] = Y[i]

This preserves sorted order in O(n) time. The same approach works for XL, XR, and Y′.

Running Time: O(n lg n)

• Presorting X and Y: O(n lg n)
• Recurrence for recursive steps: T(n) = 2T(n/2) + O(n) → T(n) = O(n lg n)
• Total: T′(n) = T(n) + O(n lg n) = O(n lg n)