Half-Plane Intersection

Role: this file is the conceptual lesson — the directed-line convention, why feasibility lives to the left, the deque-sweep invariant, and the catalogue of applications (polygon kernel, 2D LP, visibility). For a lean paste-ready implementation, see the companion contest template.

Quick Revisit

• USE WHEN: 2D linear programming, polygon kernel, feasibility region of linear constraints
• INVARIANT: deque maintains a convex intersection; front and back are trimmed by each new half-plane
• TIME: O(n log n) | SPACE: O(n)
• CLASSIC BUG: not handling parallel half-planes -- same direction keeps the more restrictive one, opposite directions means empty
• PRACTICE: ../12-practice-ladders/08-ladder-mixed.md

Computing the intersection of $n$ half-planes -- the core subroutine for 2D linear programming, polygon kernels, and feasibility regions.

Difficulty: [Advanced]Prerequisites: Geometry Basics, Convex HullCF Rating Range: 1900 -- 2100

---

Contents

1. Intuition & Concept
2. Visual Intuition -- Full Walkthrough
3. Applications
4. C++ STL Reference
5. Implementation -- Contest-Ready
6. Operations Reference
7. Problem Patterns & Tricks
8. Contest Cheat Sheet
9. Gotchas & Debugging
10. Self-Test
11. Practice Problems
12. Further Reading

---

Intuition & Concept

Layer 1 -- The Problem

You have $n$ linear constraints:

$$a_{1}x+b_{1}y\le c_1,a_{2}x+b_{2}y\le c_2,\dots ,a_{n}x+b_{n}y\le c_n$$

Find the feasible region -- the set of points $(x,y)$ satisfying all constraints simultaneously. Or determine that no such point exists.

This is 2D linear programming. Every constraint defines a half-plane (one side of a line). The feasible region is the intersection of $n$ half-planes, which is always a convex polygon (possibly unbounded, possibly empty, possibly a single point or line segment).

Layer 2 -- What Is a Half-Plane?

A half-plane is one side of a line in 2D. The line $ax+by=c$ splits the plane into two halves:

  The line ax + by = c divides the plane:

       ax + by > c            ax + by < c
       (this side)             (that side)
           .  .  .   |   .  .  .
         .  .  .  .  |  .  .  .
       .  .  .  .  . | .  .  .  .
     ---.---.---.----+----.---.---.---  <-- line ax + by = c
       .  .  .  .  . | .  .  .  .
         .  .  .  .  |  .  .  .
           .  .  .   |   .  .  .

We represent a half-plane by a directed line: the feasible side is to the left of the direction vector. This convention simplifies the algorithm.

  Half-plane: left side of directed line A -> B

             feasible
               |
       --------A--------->B------
               |
             infeasible

The direction vector is $\overrightarrow{d}=B-A$, and a point $P$ is on the feasible side iff $\text{cross}(\overrightarrow{d},P-A)>0$ (strictly left) or $\ge 0$ (left or on the line).

  Half-plane defined by directed line A->B:

  ################|
  ################|
  ## INCLUDED  ###|----->  direction A->B
  ################|
  ################|
                  |  excluded side
                  |

  (Left side of directed line is the half-plane)
  cross(d, Q-A) > 0  =>  Q is in the INCLUDED region
  cross(d, Q-A) < 0  =>  Q is on the excluded side

Layer 3 -- Why Intersections Are Convex

Each half-plane is a convex set (any line segment between two feasible points stays feasible). The intersection of convex sets is convex. So the intersection of $n$ half-planes is convex -- either a convex polygon, an unbounded convex region, or empty.

  Four half-planes intersecting to form a bounded polygon:

  Step 1: One half-plane       Step 2: Two half-planes
  (everything above line)      (a wedge)

  ########################     ############
  ########################     ##########
  ########################     ########
  ========================     ======##
                               ====
                               ==

  Step 3: Three half-planes    Step 4: Four half-planes
  (a triangle)                 (a quadrilateral)

       ########                    ####
      ##########                  ######
     ############                ########
      ##########                  ######
       ########                    ####
        ######

  Intersection of 5 half-planes = convex polygon:

         h1
        \   /  h2
         \ /
      h5--*---*
         /|    \
        / | res \  h3
       /  *-----*
      h4

  Each half-plane cuts away one side of the plane.
  The region that survives ALL cuts is always convex.

Layer 4 -- The Sort-and-Deque Algorithm

The efficient algorithm runs in $O(n\log n)$:

1. Represent each half-plane as a directed line $(p,d)$ where $p$ is a point on the line and $d$ is the direction vector. The feasible side is to the left.

2. Sort half-planes by the angle of their direction vector $d$. Use atan2(d.y, d.x) or, better, a cross-product-based comparator that avoids floating point.

3. Sweep through the sorted half-planes, maintaining a deque of active half-planes whose intersection forms the current boundary:

   For each new half-plane $h$:

   • Pop from the back while the intersection point of the last two half-planes in the deque is on the infeasible side of $h$.
   • Pop from the front while the intersection point of the first two half-planes in the deque is on the infeasible side of $h$.
   • Push $h$ to the back of the deque.

4. Final cleanup: pop from the back while the last intersection is infeasible w.r.t. the first half-plane, and vice versa.

5. The remaining deque gives the boundary of the intersection polygon. Compute vertices by intersecting consecutive half-planes.

  Deque operations during half-plane sweep:

  +---+---+---+---+---+
  | h1| h2| h3| h4| h5|  <-- sorted half-planes in deque
  +---+---+---+---+---+
    ^                 ^
  front             back

  New half-plane h6 arrives:
  - Check back:  intersection of h4,h5 outside h6? Pop h5
  - Check front: intersection of h1,h2 outside h6? Pop h1
  - Push h6 to back

  +---+---+---+---+
  | h2| h3| h4| h6|  <-- updated deque
  +---+---+---+---+
    ^             ^
  front         back

Layer 5 -- Why a Deque?

As we process half-planes in angular order, a new half-plane can eliminate boundary segments from both ends of the current intersection:

  Deque state as half-planes are added:

  deque: [h1, h2, h3, h4]
         front           back

  New half-plane h5 might:
  - Eliminate h4 from the back (h4's contribution is now interior)
  - Eliminate h1 from the front (h1's contribution is now interior)

  Result: [h2, h3, h5]

A stack wouldn't suffice because we need to remove from both ends. The deque ensures each half-plane is pushed and popped at most once -- $O(n)$ total for the sweep. The sort dominates at $O(n\log n)$.

What the Code Won't Teach You

When to recognize HPI as the right tool. The key signal is: you have a set of linear constraints of the form $ax+by\le c$ (or $\ge c$), and you need the feasible region, its area, or whether any point satisfies all of them simultaneously. This shows up in disguised form: "find the region reachable from all k sources" on a grid, or "find a point that satisfies all these distance constraints" when the constraints linearize.

The LP connection. Half-plane intersection is exactly the feasibility problem for 2D linear programming. If you know LP, you know that HPI can be solved in $O(n)$ expected time by randomized LP algorithms (Seidel's algorithm). The $O(n\log n)$ sort-based algorithm is the deterministic choice for CP. Knowing the LP connection helps you recognize when a problem is "really" an LP.

The unbounded case. If the intersection of all half-planes is unbounded (extends to infinity in some direction), many HPI implementations fail or require special handling. Bounding the problem with a large box (four half-planes at the extremes) is the standard workaround. When to apply this and how large the box should be (relative to input coordinates) is a practical detail not always in the algorithm description.

---

Visual Intuition -- Full Walkthrough

Example 1 -- Triangle from 3 Half-Planes

  h1: y >= 0             dir = (1, 0),   angle = 0
  h2: x >= 0             dir = (0, -1),  angle = -pi/2
  h3: x + y <= 4         dir = (-1, 1),  angle = 3pi/4

Sorted by angle: $h2$ ($-\pi /2$), $h1$ ($0$), $h3$ ($3\pi /4$).

  y
  4 | *
  3 | * *
  2 | * * *
  1 | * * * *
  0 +-*-*-*-*---> x
    0 1 2 3 4

  Triangle: (0,0), (4,0), (0,4)

Sweep:

  Process h2 (x >= 0): deque = [h2]
  Process h1 (y >= 0):
    Deque has 1 entry. Push. deque = [h2, h1]
  Process h3 (x + y <= 4):
    Back check: h1 /\ h2 = intersection of x=0 and y=0 = (0,0).
    Is (0,0) feasible for h3? 0 + 0 = 0 <= 4. Yes. Keep.
    Push h3. deque = [h2, h1, h3]
  Cleanup:
    Back vs front: h1 /\ h3 gives line y=0 and x+y=4, so (4,0).
    Wait, that's h1 /\ h3, but consecutive in deque are (h2,h1) and (h1,h3).
    Actually, wrap-around: check h3 /\ h2 (last and first).
    h3: x + y = 4, h2: x = 0. Intersection: (0, 4).
    Feasible for all? h1: y=4 >= 0. Yes.

Vertices: $h2\cap h1=(0,0)$, $h1\cap h3=(4,0)$, $h3\cap h2=(0,4)$. Correct triangle.

A More Interesting Example -- Quadrilateral

  h1: y >= 1             dir = (1, 0)      angle = 0
  h2: x <= 5             dir = (0, 1)      angle = pi/2
  h3: y <= 4             dir = (-1, 0)     angle = pi
  h4: x >= 2             dir = (0, -1)     angle = -pi/2
  h5: x + y <= 8         dir = (-1, 1)     angle = 3pi/4

Sorted by angle: $h4$ ($-\pi /2$), $h1$ (0), $h2$ ($\pi /2$), $h5$ ($3\pi /4$), $h3$ ($\pi$).

  y
  5 |
  4 | . +-----------+ .
  3 | . | * * * * * | .
  2 | . | * * * * * | .
  1 | . +---------+-+ .
  0 +---+--+--+--+--+---> x
    0   1  2  3  4  5  6

  The feasible region is the intersection of all five half-planes.

Sweep through sorted list:

  Process h4 (x >= 2): deque = [h4]
  Process h1 (y >= 1): push. deque = [h4, h1]
  Process h2 (x <= 5):
    Back: h4 /\ h1 = (2, 1). Feasible for h2? x=2 <= 5. Yes.
    Push. deque = [h4, h1, h2]
  Process h5 (x + y <= 8):
    Back: h1 /\ h2 = (5, 1). Feasible for h5? 5+1=6 <= 8. Yes.
    Push. deque = [h4, h1, h2, h5]
  Process h3 (y <= 4):
    Back: h2 /\ h5 = line x=5 and x+y=8, gives (5, 3). y=3 <= 4. Yes.
    Push. deque = [h4, h1, h2, h5, h3]
  Cleanup:
    Back vs front: h5 /\ h3 gives y=4 and x+y=8, so (4, 4). Feasible for h4? x=4 >= 2. Yes.
    Front vs back: h4 /\ h1 gives (2, 1). Feasible for h3? y=1 <= 4. Yes.

Final deque: $[h4,h1,h2,h5,h3]$.

Vertices:

• $h4\cap h1=(2,1)$
• $h1\cap h2=(5,1)$
• $h2\cap h5=(5,3)$
• $h5\cap h3=(4,4)$
• $h3\cap h4=(2,4)$

  y
  5 |
  4 |     E(2,4)----D(4,4)
  3 |     |            \
  2 |     |              * (5,3)=C
  1 |     A(2,1)--------B(5,1)
  0 +--+--+--+--+--+--+---> x
       0  1  2  3  4  5

A pentagon with vertices A, B, C, D, E. The constraint $x+y\le 8$ clips the upper-right corner of the rectangle $[2,5]\times [1,4]$.

Degeneracy Showcase

Half-plane intersection is dominated by degenerate cases. Three are worth working through concretely before reading the implementation.

Case 1 — parallel half-planes, same direction (one dominates):

  Constraints:   x <= 5
                 x <= 7

  +--+
  |  |  Both half-planes face left of a vertical line.
  |  |  The tighter one (x <= 5) absorbs the looser (x <= 7).
  |  |  The deque must keep only x <= 5 — emit the looser
  |  |  one and you waste a slot; emit both and the angular
  +--+  sort sees them as duplicates and breaks the sweep.
  x=5

Standard fix during the angular sort: if two consecutive half-planes have (near-)equal angle, keep whichever one places its boundary line further into the feasible side, drop the other.

Case 2 — parallel half-planes, opposite directions (empty result):

  Constraints:   x <=  3
                 x >= 7    (i.e. -x <= -7)

   //////////|         |\\\\\\\\\\
   //////////|         |\\\\\\\\\\
   //////////|         |\\\\\\\\\\
            x=3       x=7

  No point satisfies both. The deque sweep must detect that the two
  half-planes flag each other's points as infeasible, and return the
  empty polygon — *not* an arbitrary deque snapshot.

The implementation must treat "deque size < 3 at the end of the sweep" as the empty-region signal.

Case 3 — unbounded feasible region:

  Constraints:   y >= 0
                 y <= 5

  ----------------- y=5
  /////////////////
  /////////////////
  /////////////////
  ----------------- y=0
  (extends infinitely in x)

Two horizontal strips define an unbounded region. The deque algorithm cannot enumerate vertices of an unbounded polygon directly. The standard contest workaround is the bounding-box trick: prepend four half-planes x >= -M, x <= M, y >= -M, y <= M for some large M larger than any coordinate that could appear. Then every feasible region is a bounded polygon and vertex enumeration works. After computing, discard any vertices that lie on the bounding box (they are artificial) or, if the region was supposed to be bounded, treat their presence as a bug.

Read this whenever you write half-plane code. The three cases above account for the majority of contest WAs. If your output disagrees with samples by a single vertex or area, suspect parallel-handling first, empty-detection second, bounding-box artifacts third.

---

3. Applications

2D Linear Programming

Minimize $cx+dy$ subject to $n$ half-plane constraints. Find the intersection polygon, then evaluate the objective at each vertex -- the optimum is always at a vertex (or along an edge if parallel).

For unbounded feasible regions, the LP may be unbounded too. Check if the objective direction is "inside" the feasible cone.

Kernel of a Polygon

The kernel of a simple polygon is the set of all interior points from which every wall of the polygon is visible. Each wall contributes a half-plane (the side facing inward). The kernel is their intersection.

  Polygon with a non-trivial kernel:

    +--------+
    |  .  .  |       The dots represent the kernel:
    | . ** . |       points from which all walls are visible.
    |  .  .  |
    +---+    |       The notch creates a small gap, but
        |    |       the kernel still exists (shaded **).
        +----+

If the kernel is empty, no single guard can see the whole polygon.

Voronoi Cell Construction

Each Voronoi cell is the intersection of $n-1$ half-planes (one for each other site -- the half-plane closer to this site). Half-plane intersection computes a single cell in $O(n\log n)$.

Feasibility Testing

Given $n$ linear constraints, determine if any point satisfies all of them. Run half-plane intersection -- if the result is non-empty, output any vertex; otherwise output "infeasible".

---

C++ STL Reference

Function / Type	Header	What it does	Complexity
deque<HP>	<deque>	Double-ended queue for sweep	$O(1)$ push/pop
sort()	<algorithm>	Sort half-planes by angle	$O(n\log n)$
atan2(y, x)	<cmath>	Angle of direction vector	$O(1)$
vector<P>	<vector>	Store intersection polygon	$O(n)$

---

Implementation -- Contest-Ready

Half-Plane struct

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
const ld EPS = 1e-9;

struct P {
    ld x, y;
    P operator+(P o) const { return {x + o.x, y + o.y}; }
    P operator-(P o) const { return {x - o.x, y - o.y}; }
    P operator*(ld t) const { return {x * t, y * t}; }
};
ld cross(P a, P b) { return a.x * b.y - a.y * b.x; }
ld dot(P a, P b) { return a.x * b.x + a.y * b.y; }

struct HP {
    P p, d;   // point on line, direction vector
    ld angle() const { return atan2(d.y, d.x); }
};

A half-plane {p, d} represents the constraint: the feasible side is to the left of the direction vector $d$ starting from point $p$. Point $q$ is feasible iff $\text{cross}(d,q-p)>0$ (or $\ge 0$ if we include the boundary).

Line-line intersection

// Intersection point of two lines (given as half-planes).
// Assumes lines are not parallel.
P intersect(HP a, HP b) {
    ld t = cross(b.d, a.p - b.p) / cross(a.d, b.d);
    return a.p + a.d * t;
}

On the left side test

// Is point q strictly on the feasible (left) side of half-plane h?
bool on_left(HP h, P q) {
    return cross(h.d, q - h.p) > EPS;
}

Minimal contest template

// Returns the vertices of the intersection polygon (convex, CCW).
// Returns empty if intersection is empty.
// Note: does NOT handle unbounded intersections -- add bounding box if needed.
vector<P> half_plane_intersection(vector<HP> hps) {
    sort(hps.begin(), hps.end(), [](const HP& a, const HP& b) {
        return a.angle() < b.angle();
    });

    // Remove duplicate angles: keep the tighter (more restrictive) half-plane.
    // Two parallel half-planes with the same direction: the one whose line is
    // further to the left is more restrictive (smaller feasible region).
    vector<HP> uniq;
    for (auto& h : hps) {
        if (!uniq.empty() && fabs(uniq.back().angle() - h.angle()) < EPS) {
            // If uniq.back().p is on the infeasible side of h (cross < 0),
            // then h is more restrictive -- replace.
            if (cross(h.d, uniq.back().p - h.p) < 0)
                uniq.back() = h;  // h is more restrictive
        } else {
            uniq.push_back(h);
        }
    }
    hps = uniq;
    int n = hps.size();
    if (n < 3) return {};

    deque<HP> dq;
    deque<P> pts;  // intersection points between consecutive deque entries

    dq.push_back(hps[0]);
    dq.push_back(hps[1]);
    pts.push_back(intersect(hps[0], hps[1]));

    for (int i = 2; i < n; i++) {
        // Pop from back
        while (pts.size() && !on_left(hps[i], pts.back())) {
            pts.pop_back();
            dq.pop_back();
        }
        // Pop from front
        while (pts.size() && !on_left(hps[i], pts.front())) {
            pts.pop_front();
            dq.pop_front();
        }
        dq.push_back(hps[i]);
        pts.push_back(intersect(dq[dq.size()-2], dq.back()));
    }

    // Final cleanup: front vs back
    while (pts.size() >= 1 && !on_left(dq.front(), pts.back())) {
        pts.pop_back();
        dq.pop_back();
    }
    while (pts.size() >= 1 && !on_left(dq.back(), pts.front())) {
        pts.pop_front();
        dq.pop_front();
    }

    if (dq.size() < 3) return {};

    // Compute final polygon vertices
    vector<P> res;
    for (int i = 0; i < (int)dq.size(); i++) {
        int j = (i + 1) % (int)dq.size();
        res.push_back(intersect(dq[i], dq[j]));
    }
    return res;
}

Handling unbounded regions

If the intersection might be unbounded (common in LP-style problems), add a large bounding box before calling the algorithm:

void add_bounding_box(vector<HP>& hps, ld M = 1e9) {
    // Four half-planes forming a box [-M, M] x [-M, M]
    hps.push_back({{-M, -M}, {1, 0}});   // y >= -M
    hps.push_back({{ M, -M}, {0, 1}});   // x <= M
    hps.push_back({{ M,  M}, {-1, 0}});  // y <= M
    hps.push_back({{-M,  M}, {0, -1}});  // x >= -M
}

Full solution -- Polygon kernel area

Combines all pieces above. Copy P, HP, intersect, on_left, and half_plane_intersection from above, then add:

ld polygon_area(const vector<P>& poly) {
    ld area = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++)
        area += cross(poly[i], poly[(i+1)%n]);
    return fabs(area) / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> poly(n);
    for (auto& [x, y] : poly) cin >> x >> y;

    // Each edge of a CCW polygon gives an inward half-plane
    vector<HP> hps;
    for (int i = 0; i < n; i++) {
        P a = poly[i], b = poly[(i+1)%n];
        hps.push_back({a, b - a});
    }

    auto res = half_plane_intersection(hps);
    if (res.empty()) cout << "0\n";
    else cout << fixed << setprecision(6) << polygon_area(res) << "\n";
}

---

Operations Reference

Operation	Time	Space	Notes
Sort half-planes by angle	$O(n\log n)$	$O(n)$	Dominates overall complexity
Deque sweep	$O(n)$	$O(n)$	Each HP pushed/popped once
Compute intersection vertices	$O(n)$	$O(n)$	One intersection per deque pair
Overall half-plane intersection	$O(n\log n)$	$O(n)$	Sort + linear sweep
Area of result polygon	$O(h)$	$O(1)$	Shoelace formula
Feasibility check	$O(n\log n)$	$O(n)$	Non-empty result = feasible

---

Problem Patterns & Tricks

Pattern 1: "Polygon Kernel"

Given a simple polygon, find the kernel (set of points that can see all walls). Each edge generates a half-plane -- the kernel is their intersection.

// Convert polygon edges to half-planes (assuming CCW order):
vector<HP> hps;
for (int i = 0; i < n; i++) {
    P a = poly[i], b = poly[(i+1) % n];
    hps.push_back({a, b - a});
}
auto kernel = hpi(hps);
// kernel.empty() => no guard position can see all walls

CF Examples: CF 1903F, Art Gallery problem variants

Pattern 2: "2D Linear Programming"

Minimize $cx+dy$ over a half-plane intersection. Find all vertices of the feasible polygon, evaluate the objective at each.

For the LP to have a finite optimal, the feasible region must be bounded in the objective direction. Add a bounding box to ensure this.

add_bounding_box(hps);
auto poly = hpi(hps);
ld best = 1e18;
for (auto& v : poly) best = min(best, c * v.x + d * v.y);

Pattern 3: "Maximum/Minimum Area Under Constraints"

Given constraints as half-planes, maximize or minimize the area of the feasible polygon. Sometimes a parameter is optimized by binary search, with the half-plane intersection as the feasibility check.

CF Examples: CF 1906E

Pattern 4: "Intersection of Two Convex Polygons"

Each polygon is the intersection of its edge half-planes. To intersect two convex polygons, merge all half-planes and run HPI.

vector<HP> hps;
for (int i = 0; i < n; i++)
    hps.push_back({poly1[i], poly1[(i+1)%n] - poly1[i]});
for (int i = 0; i < m; i++)
    hps.push_back({poly2[i], poly2[(i+1)%m] - poly2[i]});
auto result = hpi(hps);

Pattern 5: "Binary Search + HPI Feasibility"

Binary search on a parameter (e.g., radius, distance, angle). For each candidate value, construct half-planes and check if the intersection is non-empty. This gives an $O(n\log n\cdot \log (\text{range}))$ algorithm.

CF Examples: CF 799G

Pattern 6: "Voronoi Cell via HPI"

Build the Voronoi cell for site $s_i$ by creating a half-plane for each other site $s_j$ (the perpendicular bisector, favoring $s_i$). Intersect all $n-1$ half-planes. Only practical for small $n$ or single-cell queries.

---

Contest Cheat Sheet

+================================================================+
|              HALF-PLANE INTERSECTION CHEAT SHEET               |
+================================================================+
| REPRESENTATION:                                                |
|   HP = { point p, direction d }                                |
|   Feasible side = LEFT of direction d                          |
|   on_left(h, q) = cross(h.d, q - h.p) > EPS                  |
+----------------------------------------------------------------+
| ALGORITHM:                                                     |
|   1. Sort half-planes by atan2(d.y, d.x)                      |
|   2. Dedup parallel half-planes (keep more restrictive)        |
|   3. Deque sweep: pop back/front if intersection infeasible    |
|   4. Final cleanup: back vs front                              |
|   5. Extract vertices from consecutive deque pairs             |
+----------------------------------------------------------------+
| COMPLEXITY: O(n log n) time, O(n) space                        |
+----------------------------------------------------------------+
| UNBOUNDED REGIONS: Add bounding box (4 HPs at +/- 1e9)        |
+----------------------------------------------------------------+
| POLYGON KERNEL: edges of CCW polygon -> half-planes            |
|   HP for edge i: { poly[i], poly[i+1] - poly[i] }             |
+================================================================+

---

Gotchas & Debugging

Gotcha 1: Floating-point precision

Half-plane intersection inherently uses floating point (line-line intersection, angle computation). Use long double and a generous epsilon (${10}^{-9}$). Even then, adversarial cases can break things.

using ld = long double;
const ld EPS = 1e-9;

For problems with integer coordinates, you can sometimes avoid floats in the intersection test by using exact cross products, but the final vertex computation still needs division.

Gotcha 2: Parallel half-planes

Two half-planes with the same direction angle are parallel. If their feasible regions don't overlap, the intersection is empty. The dedup step handles this: keep only the more restrictive one.

If you skip dedup, the algorithm may crash on division by zero in intersect() (since $\text{cross}(a.d,b.d)=0$ for parallel lines).

Gotcha 3: Unbounded intersections

If the half-planes don't form a bounded region, the deque may have fewer than 3 entries but the intersection is non-empty (e.g., an infinite strip). If you need to handle unbounded regions:

1. Add a large bounding box (4 half-planes).
2. Or detect the unbounded case separately.

For contest problems, adding a bounding box is almost always sufficient and much simpler.

Gotcha 4: Direction convention

The algorithm assumes "feasible = left of direction vector." For a CCW polygon, edge $A\to B$ gives direction $B-A$, with the interior on the left. For CW polygons, use $A-B$ or reverse the polygon first.

Gotcha 5: Empty and degenerate results

The algorithm returns an empty vector for empty intersections. Near-degenerate cases (single point, line segment) may give zero-area output. Check polygon_area(res) < EPS as a secondary test.

Gotcha 6: atan2 and zero-length direction

atan2 returns $(-\pi ,\pi ]$. Angles near $\pm \pi$ sort far apart but the wrap-around handles it. Also filter out half-planes with $d=(0,0)$.

Mental Traps

Trap: "HPI is just convex hull on the dual." This is technically true -- there's a duality between convex hulls and half-plane intersections -- but it's not a useful mental model for implementing HPI. The implementation is fundamentally different from hull construction: it uses a deque, processes lines not points, and requires line-line intersection calculations. Thinking "it's like convex hull" leads to code that looks like hull code but doesn't work.

Trap: "Once I sort the half-planes, the rest is mechanical." The sort is the easiest part. The deque manipulation -- when to pop from the front vs. the back -- is where the real invariant lives. The deque always stores a sequence of half-planes whose pairwise intersections form a convex chain. Maintaining this requires understanding why each pop is correct, not just pattern-matching against a template.

Trap: "This problem is asking for the intersection of regions, so it's HPI." Not all intersection-of-regions problems are HPI problems. HPI requires that each region is a half-plane (one side of a line). If the regions are circles, or arbitrary convex polygons, or more general shapes, the algorithm is different. Check that "region" = "half-plane" before applying HPI.

Trap: Ignoring degenerate inputs. HPI problems frequently have degenerate inputs: parallel half-planes, duplicate half-planes, a single half-plane, half-planes that make the intersection unbounded. None of these are "edge cases" to handle at the end -- they need to be handled in the core algorithm or the whole thing produces garbage.

Debug checklist

  [ ] Using long double (not double)?
  [ ] Epsilon large enough (1e-9) but not too large?
  [ ] Deduplicated parallel half-planes before sweep?
  [ ] Bounded the region (added bounding box if needed)?
  [ ] on_left uses strict inequality (> EPS, not >= 0)?
  [ ] Direction vectors are non-zero?
  [ ] For polygon kernel: polygon is CCW?
  [ ] Checked empty result before computing area?

---

Self-Test

Before moving on, verify you can answer these without opening the implementation above:

• [ ] Define a half-plane in code -- what data do you store to represent one? Write the struct from memory.
• [ ] Write the inside-test for a half-plane: given a half-plane H and a point P, return whether P is inside H using only cross product.
• [ ] State the three phases of the HPI algorithm (sort with tie-breaking, deque processing, wrap-around cleanup) and name the one thing that most commonly goes wrong in each phase.
• [ ] Explain why the wrap-around cleanup at the end is necessary -- sketch a concrete example of what goes wrong if you skip it.
• [ ] Name two problem types where HPI appears in disguise -- problems that don't say "half-plane intersection" but reduce to it.
• [ ] Explain why a stack is insufficient and a deque is required for the sweep phase.
• [ ] Describe what happens when two half-planes have the same boundary angle and you fail to deduplicate them.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Polygon Kernel	POJ 3130	Easy	Direct kernel via HPI
2	Art Gallery	POJ 1279	Easy	Polygon kernel area
3	How Many Families	UVa 11265	Medium	HPI for Voronoi-like regions
4	Most Distant Point	POJ 3525	Medium	Binary search + HPI feasibility
5	Video Surveillance	POJ 1474	Medium	Kernel non-emptiness check
6	Feng Shui	POJ 3384	Medium	Shrink polygon + HPI kernel
7	Half-plane Intersection	CF 1903F	Hard	Direct HPI + area computation
8	Triathlon	POJ 1755	Hard	LP in 2D via HPI
9	Triangles	CF 799G	Hard	Binary search + HPI feasibility
10	Convex Polygon Intersection	BOJ 7420	Hard	Two convex polygons via merged HPs

---

Further Reading

• cp-algorithms: Half-Plane Intersection
• CF Blog: Half-Plane Intersection in O(n log n)
• Wikipedia: Linear Programming -- 2D case
• Topcoder: Computational Geometry -- Half Planes
• Victor Lecomte, Handbook of Geometry for Competitive Programmers, Chapter on Half-Planes

Cross-references within this notebook:

• Geometry Basics -- cross product, point struct
• Convex Hull -- the dual construction (hull of points vs intersection of half-planes)
• Rotating Calipers -- queries on the result polygon

---

The Aha Moment

A half-plane is just one side of a line. The intersection of $n$ half-planes is a convex polygon (possibly unbounded). The key insight: if you sort half-planes by angle and process them with a deque, you can incrementally build the intersection boundary -- discarding half-planes that become redundant from the front or back -- in $O(n\log n)$. It's essentially a convex hull algorithm in the dual space.

Pattern Fingerprint

Fingerprint: "intersection of linear constraints in 2D" -> half-plane intersection via sorted deque

Fingerprint: "kernel of a polygon (region visible from inside)" -> half-plane intersection of inward-facing edge half-planes

Fingerprint: "feasibility of 2D linear program" -> half-plane intersection non-emptiness check

Rating Progression

CF Rating	What to Master
1200	Understand what a half-plane is (a directed line dividing the plane). Solve simple "which side of the line" problems.
1500	Implement basic half-plane intersection with the sorted-deque algorithm. Compute the kernel of a convex polygon. Check if an intersection is non-empty.
1800	Handle unbounded intersections and parallel/anti-parallel half-planes. Extract the resulting polygon's vertices from the deque. Binary search on parametric half-plane intersection problems.
2100	Incremental / online half-plane insertion. Combine HPI with binary search on the answer (parametric optimization). Solve 2D LP in $O(n)$ randomized. Duality between convex hull and half-plane intersection.

Before You Code Checklist

• [ ] Is each half-plane represented as a directed line (point + direction vector) where the "allowed" region is to the left of the direction?
• [ ] Did I sort half-planes by the angle of their direction vector using atan2, with tie-breaking that keeps the most restrictive (leftmost) half-plane?
• [ ] Does my deque-pop logic check redundancy at both the front and back before pushing a new half-plane?
• [ ] Have I handled anti-parallel half-planes (angle difference of exactly $\pi$) that can make the intersection empty?
• [ ] After processing all half-planes, did I do a final cleanup pass to remove front/back redundancies?

What Would You Do If...?

Scenario 1: The problem asks whether a point exists that is inside all $n$ given half-planes (feasibility check).

Answer: Run the half-plane intersection algorithm. If the deque is non-empty at the end (i.e., the resulting region has at least one vertex or is unbounded but valid), the answer is "yes." No need to explicitly compute the polygon -- just check that the deque has $\ge 2$ half-planes after the final cleanup.

Scenario 2: You need the area of the intersection, but the intersection could be unbounded.

Answer: Add four bounding-box half-planes that form a huge rectangle enclosing all relevant geometry (e.g., coordinates $\pm {10}^9$). These clip the unbounded region into a finite polygon. Then run HPI and compute the polygon's area with the shoelace formula. The bounding box doesn't affect correctness if chosen large enough.

Scenario 3: Your HPI gives the wrong polygon -- it's missing a vertex.

Answer: The most likely cause: when two half-planes have the same angle (parallel, same direction), you must keep only the more restrictive one and discard the other before the deque processing. If both survive into the deque, the intersection line computation between them is undefined (parallel lines don't intersect), and a vertex is lost or corrupted.

The Mistake That Teaches

I was solving a problem: "Given a convex polygon, find the area of its kernel" (the set of points from which the entire polygon boundary is visible). I knew the kernel is the intersection of half-planes -- one per edge, facing inward.

My HPI code worked on all hand-crafted tests. Then on the judge's test 23, I got a negative area. Negative area? That's impossible for a valid polygon.

After hours of debugging, I found the issue: my half-planes were directed along each edge using (polygon[i+1] - polygon[i]), but the polygon was given in clockwise order. "Left of the direction" was therefore outside the polygon, not inside. I was intersecting the complement of what I wanted.

The fix was trivial: reverse the polygon (or negate each direction vector). But the symptom was bizarre -- the shoelace formula gave a negative area because the resulting "polygon" vertices were in clockwise order, which is the shoelace formula's way of saying "you got the orientation wrong." Lesson: always verify your polygon's winding order before generating half-planes. A single sign error inverts the entire problem.

Debug This

Bug 1: This half-plane intersection drops valid half-planes and produces a wrong polygon.

void addHalfPlane(deque<Line>& dq, deque<Point>& pts, Line l) {
    while (pts.size() && cross(l.dir, pts.back() - l.p) < 0) {
        dq.pop_back(); pts.pop_back();
    }
    while (pts.size() && cross(l.dir, pts.front() - l.p) < 0) {
        dq.pop_front(); pts.pop_front();
    }
    dq.push_back(l);
    if (dq.size() > 1)
        pts.push_back(intersect(dq[dq.size()-2], dq[dq.size()-1]));
}

What's the bug?

The comparison cross(l.dir, pts.back() - l.p) < 0 uses strict inequality. A point exactly on the half-plane boundary (cross product = 0) is considered valid and not popped. But when two half-planes produce an intersection point exactly on the boundary of a third, that point should be treated as redundant (or at least handled consistently). Use <= 0 if the convention is strict half-plane interior, or < 0 if boundary is included -- but be consistent. The typical bug is that < 0 here combined with <= 0 elsewhere (or vice versa) produces missed pops.

Bug 2: This HPI crashes with a floating-point exception on some inputs.

Point intersect(Line a, Line b) {
    double t = cross(b.dir, a.p - b.p) / cross(a.dir, b.dir);
    return {a.p.x + t * a.dir.x, a.p.y + t * a.dir.y};
}

vector<Point> hpi(vector<Line> lines) {
    sort(lines.begin(), lines.end(), [](const Line& a, const Line& b) {
        return atan2(a.dir.y, a.dir.x) < atan2(b.dir.y, b.dir.x);
    });
    deque<Line> dq;
    deque<Point> pts;
    for (auto& l : lines) {
        addHalfPlane(dq, pts, l);
    }
    // ... final cleanup and extract polygon
}

What's the bug?

When two half-planes have the same angle (parallel, same direction), cross(a.dir, b.dir) is zero, causing a division by zero in intersect(). Before pushing a new half-plane, you must check if it has the same angle as the previous one in the deque. If so, keep only the more restrictive one (the one whose boundary line is further left). Add a same-angle check:

if (dq.size() && sameAngle(dq.back(), l)) {
    if (cross(l.dir, dq.back().p - l.p) >= 0)
        return; // existing is more restrictive, skip new
    dq.pop_back();
    if (pts.size()) pts.pop_back();
}

Bug 3: This HPI produces an extra spurious vertex in the output polygon.

// After processing all half-planes:
// Final cleanup
while (pts.size() && cross(dq.front().dir, pts.back() - dq.front().p) < 0) {
    dq.pop_back(); pts.pop_back();
}
// Extract polygon vertices
vector<Point> result(pts.begin(), pts.end());
result.push_back(intersect(dq.back(), dq.front()));

What's the bug?

The final cleanup only removes half-planes from the back that are redundant with respect to the front. But it doesn't check whether the front is redundant with respect to the back. After popping from the back, the intersection of the new back with the front changes. You also need:

while (pts.size() && cross(dq.back().dir, pts.front() - dq.back().p) < 0) {
    dq.pop_front(); pts.pop_front();
}

Without this, a stale half-plane at the front of the deque generates a spurious intersection vertex with the back half-plane, producing an extra incorrect vertex in the output polygon.

Historical Origin

Half-plane intersection algorithms trace back to the 1970s-80s work on computational geometry and linear programming. The $O(n\log n)$ sorted-deque approach was formalized in the context of incremental convex polygon intersection. The observation that half-plane intersection is dual to convex hull construction -- points map to lines and vice versa -- is a cornerstone of geometric duality theory popularized by Edelsbrunner (1987).

Mnemonic Anchor

"Half-planes are walls. Sort them by which way they face, then sweep — each new wall either tightens the room or proves it's been sealed shut."

Common Mistakes

• Parallel half-planes not deduplicated. Same-direction parallels: keep only the more restrictive one. Opposite-direction: the intersection is empty — detect, do not compute.
• Dividing by zero in line intersection. When cross(a.dir, b.dir) == 0 the lines are parallel — guard before dividing.
• Unbounded intersection not handled. If the feasible region is unbounded, prepend four bounding half-planes (a large box) before the sweep, then check for box-vertex artifacts in the result.
• Floating-point precision in angle sorting. atan2 is convenient but loses precision exactly when half-planes are nearly parallel — which is precisely when correctness depends on the comparison. Prefer cross-product-based angle ordering, especially for integer inputs.
• Wrong tiebreaker for same-angle half-planes. Must keep the more restrictive (leftmost) plane, not the less restrictive one.
• Skipping the final cleanup pass. The last few half-planes can invalidate the front of the deque; without a back-vs-front cleanup the polygon contains spurious vertices.

---

Recap and Cross-Links

Concept	Link
Geometry Basics	01-geometry-basics
Convex Hull	02-convex-hull
Rotating Calipers	03-rotating-calipers
Practice	Ladder - Mixed