Advanced Algorithms and Network Flow

This guide explores the foundational and advanced concepts of Module 4, covering computational
geometry, network flow theory, randomized graph algorithms, and string processing. These topics form
the backbone of modern optimization, spatial indexing, and data retrieval systems.

1. Computational Geometry: Spatial Structures and Arrangements

Computational geometry focuses on the design and analysis of algorithms for geometric problems. At its
core, it deals with how we represent and query spatial data efficiently.

 Point Location The Point Location problem asks: given a planar subdivision (a map divided into
regions by edges and vertices) and a query point q , which region contains q ?

 Slab Method: Divide the plane into vertical slabs by drawing vertical lines through every vertex.
Within each slab, edges do not intersect and can be ordered vertically. This allows O(logn)
2
query time but can take O(n ) space.
 Trapezoidal Maps: A more efficient approach using a randomized incremental algorithm to build
a search structure. It achieves O(logn) expected query time with O(n) expected space.

 Convex Hulls The Convex Hull of a set of points P is the smallest convex polygon that contains
all points in P. Think of it as a rubber band snapped around a set of nails.
 Graham Scan: Uses a stack to maintain the hull, sorting points by angle. Complexity: O(n logn) .

 Chan’s Algorithm: An “output-sensitive” algorithm that combines Graham Scan and Jarvis March
to achieve O(n logh) time, where h is the number of points on the hull.

 Voronoi Diagrams and Delaunay Triangulations A Voronoi Diagram partitions a plane into
regions based on distance to a specific set of points (sites). For each site, its Voronoi cell consists
of all points closer to it than to any other site.

 Duality: The dual of a Voronoi diagram is the Delaunay Triangulation. An edge exists between
two sites in the triangulation if their Voronoi cells share a boundary.

 Fortune’s Algorithm: A sweep-line algorithm that constructs the Voronoi diagram in O(n logn)
time.
  Arrangements An Arrangement A(L) is the subdivision of the plane induced by a set of lines L
. It consists of vertices (intersections), edges (segments of lines), and faces (regions). For n lines,
2
the complexity of the arrangement is O(n ).

2. Network Flow and Matching

Network flow theory deals with transporting a “commodity” through a graph from a source to a sink
under capacity constraints.

 Maximum Flow Problem Given a directed graph G=(V , E) with a source s, a sink t , and
capacities c (u , v )≥0 , find the maximum amount of flow f that can be sent from s to t .
 Capacity Constraint: For all (u , v )∈ E , 0 ≤ f (u , v)≤ c (u , v ).

 Flow Conservation: For all v ∈ V ¿ s , t }¿, ∑ f (u , v )=∑ f (v , w).

u w
 The Ford-Fulkerson Algorithm This algorithm iteratively finds an Augmenting Path in the

Residual Network G f .

 The residual capacity c f (u , v ) is defined as:

c f (u , v )=
{
c (u , v )− f (u , v) if (u , v )∈ E
f (v , u) if (v ,u)∈ E

 The algorithm terminates when no path exists from s to t in Gf .

 Max-Flow Min-Cut Theorem A fundamental result stating that the value of the maximum flow is
equal to the capacity of the Minimum Cut. A cut (S , T ) partitions vertices such that s ∈ S and
t ∈ T . The capacity is the sum of capacities of edges crossing from S to T .
 Maximum Bipartite Matching A Matching in a bipartite graph G=(U ∪V , E) is a set of edges
with no shared endpoints. We can solve this by reducing it to Max-Flow:

1. Add a source s and sink t .

2. Add directed edges from s to all u ∈U with capacity 1.

3. Add directed edges from all v∈V to t with capacity 1.

4. Direct original edges from U to V with capacity 1.

5. The max flow value equals the size of the maximum matching.
3. Graph Partitioning and Randomized Algorithms

 Karger’s Min-Cut Algorithm A randomized algorithm to find the minimum cut of a graph. It
uses the concept of Edge Contraction.

 Algorithm:

1. Pick an edge (u , v ) uniformly at random.

2. Contract u and v into a single super-node, removing self-loops but keeping multi-edges.
3. Repeat until only 2 nodes remain.

4. The edges between these two nodes represent a candidate min-cut.

 Success Probability: The probability of finding the actual min-cut is at least 2/(n(n −1)). By
2
running the algorithm O(n log n) times, we can find the min-cut with high probability.
  Multicommodity Flow Unlike standard flow, Multicommodity Flow involves multiple different
commodities, each with its own source and sink, sharing the same network capacities. This is
used in graph partitioning to find “bottlenecks” that divide a graph into clusters with high
internal connectivity and low external connectivity.

4. String Matching and Document Processing

String algorithms are essential for text editors, search engines, and bioinformatics.

 Exact String Matching Find all occurrences of a pattern P of length m in a text T of length n .

 Knuth-Morris-Pratt (KMP): Uses a prefix function π to avoid redundant comparisons. Time

complexity: O(n+ m).

 Boyer-Moore: Matches from right to left and uses “bad character” and “good suffix” shifts to skip
large portions of the text. Often faster in practice than KMP.

 Suffix Structures For complex queries (like finding the longest repeated substring), we use:

 Suffix Tree: A compressed trie of all suffixes of a string. Provides O(m) search time for a pattern

of length m .

 Suffix Array: A sorted array of all suffixes. More space-efficient than Suffix Trees, often used with
the LCP Array (Longest Common Prefix).

 Document Processing Involves algorithms for Inverted Indices (mapping words to document
IDs) and TF-IDF (Term Frequency-Inverse Document Frequency) to rank document relevance.

Summary Table of Complexities

Algorithm Problem Time Complexity

Graham Scan Convex Hull O(n log n)

Fortune’s Voronoi Diagram O(n log n)

Edmonds-Karp Max Flow O(V E )

2

Karger’s Min Cut 2

O(n log n) (for high prob)

KMP String Matching O(n+ m)

Assumptions and Context

 All graphs are assumed to be connected unless otherwise stated.

 For geometric algorithms, we assume “general position” (no three points are collinear, no four
points are cocircular) to simplify the explanation of edge cases.

 In flow networks, capacities are assumed to be non-negative integers for the convergence of
basic Ford-Fulkerson.