Paper Cuts ✂

It started with a movie scene.

You know that trope — someone feeds a stack of documents into a shredder. Long strips of paper rain down. Then, in the next scene, a forensics team (or some obsessive CS guy) reconstructs the original pages from those strips.

The CS version of that is actually a real problem: given a set of rectangular strips with known widths and edge features, reconstruct the original document. People have built solvers for it. It's basically a constrained jigsaw puzzle with a known shape vocabulary.

But I started wondering about a different direction. Not reconstruction, but decomposition. What if instead of strips, we had arbitrary straight cuts? And instead of asking "reassemble this," we asked more fundamental questions first — about how you even represent the problem?

This is what I'm calling Paper Cuts.

Let's start concrete. A square page.

Take a unit square — the page is [0,1] × [0,1]. Now make some straight cuts. Each cut goes all the way across (for now). Here's what we're dealing with:

Okay, so what's the actual problem?

Here's a rough first-pass formulation. Treat it as a sketch, not a spec — the interesting part is all the design questions hiding inside it.

// Paper Cuts — Problem Statement v0.1

Input:
  page   → a rectangle (e.g. unit square [0,1]×[0,1])
  cuts   → a set of line segments, each defined by
           two points on the boundary of the page

Output:
  a set of regions (polygons) such that:
    • every point on the page belongs to exactly one region
    • no region is split by any cut
    • the union of all regions = the original page

Constraints:
  ??? ← this is where it gets interesting

Those ??? are doing a lot of work. Let's unpack them.

The design questions.

Before you think about the algorithm, you have to answer a bunch of representational questions. I've been sitting with these for a while and they're genuinely non-trivial:

1 · Input Representation

• Do cuts always span the full width/height of the page? If yes, every cut can be represented as a single boundary-to-boundary line. If no, you have partial cuts — and suddenly half-cuts become their own thing.
• Are cuts defined by two boundary points, or by a line equation? Two points is more concrete but has precision issues. A line equation is clean mathematically but less intuitive as input.
• Can two cuts share an endpoint on the boundary? A "fan" of cuts from one corner point. Is that valid? How does your structure handle coincident boundary nodes?

2 · Duplicates and Degeneracies

• Do duplicate cuts (same line, listed twice) cause issues? A robust solution should be idempotent — cutting along the same line twice shouldn't produce zero-width regions or explode.
• What about three cuts that all meet at a single interior point? In PSLG theory this is a vertex of degree 6. Some algorithms need special-casing for this. Do you?
• Are collinear cuts (one cut extending another) allowed? This one is sneaky. Two collinear segments effectively form one cut — but your input doesn't say that explicitly.

3 · Output Representation

• How do you represent a region? Ordered list of vertices? Half-edge structure? Something else? The answer affects how you check adjacency, compute area, or re-assemble later.
• Should adjacent regions share edge objects, or each have their own copy? Shared edges = DCEL (Doubly Connected Edge List). Two copies = simpler to build, but you lose adjacency info. Which matters for your use case?
• What's the canonical ordering of regions in the output? By area? By top-left corner? This determines whether two "equivalent" decompositions compare equal — which matters a lot if you want to test or hash solutions.

4 · Rotations and Equivalence

• Are two cut sets "equivalent" if one is a rotation of the other? Rotating the page 90° before cutting gives different coordinate sets but the same physical result. Do you care?
• Should piece shapes be compared up to rotation, reflection, or translation? This is the reassembly variant — if you want to later solve "given pieces, reconstruct the page," you definitely need a canonical piece representation that's invariant to rigid transforms.

One way to think about it: a planar graph

Here's the framing I keep coming back to. Every valid set of cuts induces a planar straight-line graph on the page:

Every cut endpoint on the boundary is a graph node. Every intersection of two cuts is also a graph node. The cuts themselves become edges. The faces of the resulting planar graph — everything except the outer infinite face — are exactly the pieces you get when you scatter the cuts.

Some cases worth thinking about

The T-junction case is particularly sneaky. The half-cut goes from the boundary to another cut — it doesn't exit through the other side. This does still divide regions: the top half gets split into two, but the bottom half is untouched, giving 3 regions total (not 2). Now the question for your algorithm is whether a T-junction endpoint is treated differently from a full intersection node — in PSLG terms, v has degree 3 instead of 4, which changes the face-walking logic.

What I've figured out so far

The harder variant: re-assembly

Once you can go from cuts → regions, you can flip it. Given an unlabeled set of polygonal pieces (no coordinates, just shapes), can you determine if they came from a single rectangular page? And if so, how many cuts were made, and where?

This is the shredder problem — and it's substantially harder. You'd need to:

1. Define a canonical representation for each piece that's invariant to translation (and maybe rotation).
2. Find edge matchings — two pieces are adjacent if they share an edge of equal length.
3. Verify that the assembled configuration tiles into a valid rectangle.
4. Decide whether reflected/rotated pieces count as "the same."