We present a complete classification of all minimal problems for generic arrangements of points and lines completely observed by calibrated perspective cameras. We show that there are exactly 30 minimal problems in total, with constraints that no problems exist for more than 6 cameras, for more than 5 points, and for more than 6 lines. We determine the algebraic degrees of each of these problems — indicating the number of solutions and the intrinsic difficulty of the problem. We demonstrate that several new minimal problems have small degrees that might be practical in image matching and 3D reconstruction.

Minimal problems play fundamental roles in computer vision applications. They are essential for 3D reconstruction, image matching, visual odometry and visual localization. Over the years, "many minimal problems have been described and solved and new minimal problems are constantly appearing." Despite this, a systematic and complete enumeration has not been achieved. This paper provides "a complete classification of minimal problems for generic arrangements of points and lines, including their incidences, completely observed by any number of calibrated perspective cameras." Notably, 26 of the 30 minimal problems identified are new, previously undiscovered.

We "consider calibrated scenarios since it avoids many degeneracies" inherent in uncalibrated setups. Our focus is on "complete visibility" — meaning "all points and lines are observed in all images and all observed information is used." This assumption, while restrictive, enables a mathematically rigorous and exhaustive classification. We employ a sequence of tests for detecting minimality starting with counting degrees of freedom and ending with full symbolic and numeric verification. The result is a definitive catalogue of all possible minimal configurations.

A "point-line problem" is formally defined as a tuple (p, l, I, m) specifying that p points and l lines in space are projected to m views, where I encodes the incidence relations among points and lines. The authors establish two key mathematical objects: the "variety of point-line arrangements" X_{p,l,I} and the "image variety" Y_{p,l,I,m}. A point-line problem is minimal when "a generic image tuple in Y_{p,l,I,m} has a nonzero finite number of solutions." This requires the joint camera map to be dominant and to produce finite preimages.

A necessary condition for minimality is the "balance condition": dim(X_{p,l,I} x C^m) = dim(Y_{p,l,I,m}). For balanced problems, this translates to the equation: 3p_f + p_d + 4l_f + 2l_a + 6m - 7 = m(2p_f + p_d + 2l_f + l_a), where p_f denotes free points, p_d dependent points, l_f free lines, and l_a adjacent lines. This dimension-counting formula serves as the first filter in the systematic search — any candidate problem must satisfy this arithmetic constraint before further verification.

The methodology uses "direct geometrical determinantal constraints" rather than multi-view tensors to eliminate world variables. Two types of constraints generate the equation systems. Line Correspondence (LC): if lines l_1, ..., l_m are images of the same world line, then rank[P_1^T l_1 ... P_m^T l_m] <= 2. Common Point (CP): planes derived from line projections must share a common line, enforced through rank constraints on associated matrices. The authors then apply Algorithm 1 (Jacobian rank computation) to verify if the projection map is dominant, confirming minimality via the condition rank J(C_0, Y_0) = 6m - 7.

For computing algebraic degrees — the number of solutions to each minimal problem — the authors employ two complementary strategies. For problems with 2-3 views, they compute Groebner bases to obtain exact solution counts. For higher-dimensional problems, they use "the monodromy method, a technique based on numerical homotopy continuation" from numerical algebraic geometry. This dual approach ensures that both symbolic exactness and computational feasibility are achieved across the full range of problems.

The complete classification yields 30 minimal problems distributed across camera counts: 6 cameras: 1 problem; 5 cameras: 3 problems; 4 cameras: 6 problems; 3 cameras: 17 problems; 2 cameras: 3 problem classes. Key theoretical results include Lemma 1, establishing that "every balanced point-line problem with at least five points has exactly two cameras"; Theorem 1, proving there is "no balanced point-line problem with seven or more cameras"; and Theorem 2, demonstrating there are "34 balanced point-line problems with 3, 4, 5 or 6 cameras" (of which 30 pass all minimality tests).

The algebraic degrees of the 30 problems span a wide range: the smallest degrees are 5, 12, 16, and 20 (two-view problems); moderate degrees include 32, 40, and 64 (potentially practical); while larger degrees reach 240 to 4512 and beyond (higher view counts). Notably, the calibrated homography problem (3-point, 0-line, 2-view) has degree 5, and the classical 5-point problem (5-point, 0-line, 2-view) has degree 20. The authors emphasize that "several new minimal problems have small degrees," making them "practical in image matching and 3D reconstruction."

This work represents "a step towards a complete characterization of all minimal problems for points, lines and their incidences in calibrated multi-view geometry." The discovery of 26 new minimal problems, several with computationally tractable solution counts, opens the door to "constructing efficient solvers" for practical applications. The authors acknowledge that the complete visibility constraint limits applicability, noting that "full account for partial visibility is a much harder task and will be addressed in the future." Extending the classification to uncalibrated cameras and partial observations remains an important open direction.