Half-plane Intersection

Compute the region that lies inside every half-plane of a set. That region is always a convex polygon (or empty / unbounded). We want its vertices.

This lesson follows CP-Algorithms — Half-plane intersection (Sort-and-Incremental, O(N log N)).

Prerequisites: points, vectors, line intersection, orientation (cross). Convex hull / CHT help intuition but are optional.

Definitions

• N = number of half-planes.
• Represent a half-plane by a point p on its boundary and direction vector pq. The allowed region is to the left of pq. The angle of the half-plane is the polar angle of pq.
• Assume the answer is bounded or empty. For unbounded cases, add four half-planes of a large bounding box.
• For simplicity assume no parallels first; parallels are handled specially later.

Example: y ≥ 2x − 2 as point P = (1, 0) with direction PQ = (1, 2).

Check: definitions

Quiz

Half-plane definitions

1 / 4

Allowed side of each half-plane in this article is…

Pick an answer to see if you are right.

Brute force — O(N³)

Intersect every pair of supporting lines (O(N²) points). Keep a point only if it lies in all half-planes (O(N) each). Convex-hull the survivors.

Vertices of the true intersection are among those pairwise intersections, so this is correct — and fine only for tiny N or “is empty?” checks.

Incremental cutting — O(N²)

Start from a big box. Cut the current convex polygon by each half-plane in turn (find the two edge intersections, replace the discarded chain). Each cut is O(N) → O(N²) total.

Good intuition; still too slow when N is large.

Sort-and-Incremental — O(N log N)

Attributed to Zeyuan Zhu’s 2006 CTOC thesis (New Algorithm for Half-plane Intersection and its Practical Value). Variant below builds the whole intersection in one angle-sorted pass with a deque.

Key observation

The final boundary walks half-planes in increasing angle. If you insert half-planes in that order into a deque, newly redundant planes only appear at the front or back — never in the middle.

At step k (planes 1..k−1 already in the deque):

1. Pop back while the back plane is redundant w.r.t. the new one.
2. Pop front while the front plane is redundant.
3. If the deque collapses to empty → empty intersection.
4. Push the new half-plane.

A plane is redundant if removing it does not change the intersection (its adjacent vertex already lies outside the new plane).

Parallels

• Opposite parallels: with a bounding box, opposite planes are not adjacent after sorting. If they become adjacent after pops, the intersection is empty — detect via dot(pqᵢ, pqⱼ) < 0 and stop.
• Same angle: keep only the leftmost (strictest) half-plane; drop the others.

Outline

1. Add bounding-box half-planes; sort by angle — O(N log N).
2. Deque insert with front/back pops — amortized O(N) (each plane enters/leaves once).
3. Final wrap-around cleanup (front vs back).
4. Vertices = intersections of adjacent remaining planes — O(N).

If planes are already angle-sorted (e.g. edges of one convex polygon), skip sorting → linear time.

Check: algorithm

Quiz

Half-plane intersection algorithm

1 / 4

Sort-and-Incremental complexity is…

Pick an answer to see if you are right.

Interactive walkthrough

Four half-planes of a convex quad, inserted in angle order.

Implementation

Point and half-plane

const long double eps = 1e-9, inf = 1e9;

struct Point {
    long double x, y;
    explicit Point(long double x = 0, long double y = 0) : x(x), y(y) {}
    friend Point operator+(const Point& p, const Point& q) {
        return Point(p.x + q.x, p.y + q.y);
    }
    friend Point operator-(const Point& p, const Point& q) {
        return Point(p.x - q.x, p.y - q.y);
    }
    friend Point operator*(const Point& p, const long double& k) {
        return Point(p.x * k, p.y * k);
    }
    friend long double dot(const Point& p, const Point& q) {
        return p.x * q.x + p.y * q.y;
    }
    friend long double cross(const Point& p, const Point& q) {
        return p.x * q.y - p.y * q.x;
    }
};

struct Halfplane {
    Point p, pq;
    long double angle;
    Halfplane() {}
    Halfplane(const Point& a, const Point& b) : p(a), pq(b - a) {
        angle = atan2l(pq.y, pq.x);
    }
    // Allowed region = LEFT of directed line.
    bool out(const Point& r) {
        return cross(pq, r - p) < -eps;
    }
    bool operator<(const Halfplane& e) const { return angle < e.angle; }
    friend Point inter(const Halfplane& s, const Halfplane& t) {
        long double alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq);
        return s.p + (s.pq * alpha);
    }
};

Algorithm

vector<Point> hp_intersect(vector<Halfplane>& H) {
    Point box[4] = {
        Point(inf, inf), Point(-inf, inf),
        Point(-inf, -inf), Point(inf, -inf)
    };
    for (int i = 0; i < 4; i++)
        H.push_back(Halfplane(box[i], box[(i + 1) % 4]));

    sort(H.begin(), H.end());
    deque<Halfplane> dq;
    int len = 0;
    for (int i = 0; i < (int)H.size(); i++) {
        while (len > 1 && H[i].out(inter(dq[len - 1], dq[len - 2]))) {
            dq.pop_back(); --len;
        }
        while (len > 1 && H[i].out(inter(dq[0], dq[1]))) {
            dq.pop_front(); --len;
        }
        if (len > 0 && fabsl(cross(H[i].pq, dq[len - 1].pq)) < eps) {
            if (dot(H[i].pq, dq[len - 1].pq) < 0.0)
                return {};
            if (H[i].out(dq[len - 1].p)) {
                dq.pop_back(); --len;
            } else continue;
        }
        dq.push_back(H[i]); ++len;
    }
    while (len > 2 && dq[0].out(inter(dq[len - 1], dq[len - 2]))) {
        dq.pop_back(); --len;
    }
    while (len > 2 && dq[len - 1].out(inter(dq[0], dq[1]))) {
        dq.pop_front(); --len;
    }
    if (len < 3) return {};
    vector<Point> ret(len);
    for (int i = 0; i + 1 < len; i++)
        ret[i] = inter(dq[i], dq[i + 1]);
    ret.back() = inter(dq[len - 1], dq[0]);
    return ret;
}

🧪 Triangle half-planes → three vertices

Implementation notes

• Multiple planes through one vertex can yield duplicate adjacent vertices. Harmless for emptiness / area; unique them if needed. Keep duplicates mid-algorithm so zero-area cases (point / segment) stay correct.
• Constraints ax + by + c ≤ 0: either adapt the struct or sample two points per line. Prefer the input form to limit precision loss.

Applications

Task	Idea
Intersection of convex polygons	Each edge → half-plane; intersect all — O(S log S) for total sides S
Kernel of a simple polygon	Can you see the whole boundary from an interior point? Half-planes of edges
Ordered visibility of points	See pᵢ left of pᵢ₊₁ ↔ half-plane of segment pᵢpᵢ₊₁; nonempty intersection?
Largest inscribed circle in convex P	Binary search radius r; shrink each side inward by r; check nonempty (angles already sorted → O(NK))
2D linear programming	Feasibility = half-plane intersection; optimize linear f with binary search / CHT-like queries on the feasible polygon

There is also a simple randomized LP algorithm for 2-variable constraints (CG lecture, Petr’s half-plane week).

Check: applications

Quiz

Applications

1 / 4

Kernel of a polygon is…

Pick an answer to see if you are right.

Practice drills

Activity: Outside test

Line through px py toward qx qy; allowed = left. Point rx ry. Print OUT if outside, else IN.

Contest problems

From CP-Algorithms:

• Codechef CHN02 — Animesh decides to settle down
• POJ 3130 — How I Mathematician Wonder What You Are!
• POJ 3335 — Rotating Scoreboard
• POJ 1474 — Video Surveillance (kernel nonempty?)
• POJ 1279 — Art Gallery
• POJ 2451 — Uyuw's Concert

References

• Zeyuan Zhu — New Algorithm for Half-plane Intersection
• Artem Vasilyev — Brazilian ICPC Summer School 2020
• Petr Mitrichev — A half-plane week

Cheat sheet

Piece	Takeaway
Goal	Convex region ∩ all half-planes
Naive	O(N³) pairwise points
Cut	O(N²) incremental
Fast	Sort by angle + deque pops — O(N log N)
Parallel	Opposite → empty; same → keep leftmost
Unbounded	Add bounding box
Apps	Kernels, convex ∩, 2D LP, binary-search offsets