Waltz Line Labeling
Label every edge as convex, concave or arrow — the CSP that proves a 2D drawing can (or cannot) depict a real 3D trihedral object
The Simplest Explanation
A 2D line drawing of trihedral objects (every vertex where 3 faces meet, like cubes) is valid iff every edge can be labeled consistently:
+convex (outer edge)-concave (inner fold)→arrow (occluding edge)
Constraints come from junctions — points where edges meet. Only certain label combinations are physically possible at each junction type.
Valid drawing = all junctions assigned one of their legal label patterns and adjacent junctions agree on shared edges. If any junction has empty domain → whole drawing is NIL.
Junction Catalog
Each junction carries a unique label you must output (L1, W1, Y3, T4 etc.):
| Type | Shape | Legal patterns |
|---|---|---|
| L | 2 edges (corner) | + +, - -, + - variants |
| W | 3 edges (one 180° gap) | Specific +/arrow combos |
| Y | 3 edges (120° each) | All + or arrow patterns |
| T | 3 edges (T-junction = occlusion) | Arrow must point along stem |
In-plane rotations are also valid.
Waltz Filtering
- Initialize: For each junction, domain = all legal labelings for its type
- Pick a junction/edge (any order)
- Constrain: Remove labelings that conflict with already-labeled neighbors on shared edges
- If any domain empties → NIL (inconsistent) — reset all to NIL per papers
- Repeat until stable or all labeled
This is arc consistency on junctions.
Exam Questions
Valid vs NIL:
- 23T1 FN: Drawing with junctions 1-4 → answer
Y3,L5,L4,T3for valid,NILfor impossible - 23T2 AN Q7.1: Valid →
Y1,W1,L5,T4, invalid →NIL
How to solve by hand:
- List each dot's degree → deduce type (2=L, 3 wide=W, 120/120/120=Y, T-shape=T)
- Write possible label sets for each type
- Propagate: shared edge must have same label (+/-/arrow) at both ends
- If empty → output
NIL