Walter Whiteley The Decline and Rise of Geometry in 20th Century North America, 1999
Sugihara's Theorem
By now we have studied three necessary conditions for the realizability problem, all of them seem very nice but regretly not sufficient for solving this problem. Within the period 19821984 Sugihara finally proposed a complete set of constraints that characterizes realizable line drawings. These are derived as follows:
Step one: First, the labeling of the edges is used.
Step two: Then, the spatial structure is derived from the edge labels: a set of abstract triples expressing position relationships between vertices and faces. There are two types of triples:
 Vertexface triples of the form (v, r, f ), where v is a vertex of the drawing, f is a face, and r is a relationship giving the position of v relative to f . The possible values for r are"ON", "STRICTLY ABOVE", "STRICTLY BELOW", "ABOVE", and "BELOW",according to wherev must lie exactly on the faceplane f , or strictly above/below f, or above/below f but possibly on f too, respectively.
 Vertexvertex triples of the form(v_{i}, r, v_{j}), where v_{i }and v_{j }are vertices and r is a relationship giving the position of v_{i }relative to v_{j}. The possible value for r are, "ABOVE", and "BELOW", depending on whether the zcoordinate of v_{i }is greater than that of v_{j }or conversely.
According to the labels every vertex and edge produce a number of such triples, as shown in the following figure:












Figure: The Spatial Structure.
Step three: translate them into an algebraic constraint, as indicated in the following table:




( v ON f )
( v ABOVE f ) ( v BELOW f ) ( v STRICTLY ABOVE f ) ( v STRICTLY BELOW f ) 
(v_{x}, v_{y},
v_{z},
1) * (A_{f }, B_{f }, 1, D_{f })^{t }
= 0
(v_{x}, v_{y}, v_{z}, 1) * (A_{f }, B_{f }, 1, D_{f })^{t} >= 0 (v_{x}, v_{y}, v_{z}, 1) * (A_{f }, B_{f }, 1, D_{f })^{t} =< 0 (v_{x}, v_{y}, v_{z}, 1) * (A_{f }, B_{f }, 1, D_{f })^{t} > 0 (v_{x}, v_{y}, v_{z}, 1) * (A_{f }, B_{f }, 1, D_{f })^{t} < 0 

(v_{i} ABOVE v_{j})
(v_{i} BELOW v_{j}) 
v_{1z } v_{2z}
>= 0
v_{1z} v_{2z }=< 0 
Table: Translation of incidence triples.
There, v_{x}, v_{y }and v_{z }are the coordinates of vertex v, and A_{f }, B_{f }and D_{f }are the plane coefficients of face f . These constraints are linear, since v_{x }and v_{y }are known and equal to the coordinates of the corresponding junction in the drawing. If we have n vertices and m faces, then there are 3m+n unknowns. We can collect them in a (3m+n)tuple W, and write all equations in matrix form as:
Theorem: For a typePAK problem with Assumptions O1, W2, D1 and D2, a polyhedron is realizable if and only if there is a solution of the linear system consisting of eq. (1) and ineq. (2).
We can see, this is a Necessary
and Sufficient Condition for the Realizability.
Problem with it
Sugihara's theorem gives a method for judgement of the realizability.
However it is too strict from a practical point of view, slight perturbations
of vertex positions can make a line drawing incorrect. In the realistic
application, it is impossible to guarantee the exact position of objects
in a scene. As we have mentioned before, in that Truncated
Pyramid Question, figure (a) is generically reconstructible. So, some
uncertainty must be taken into consideration. In order to correct super
strict incorrect pictures, Sugihara proposes a nice solution: to delete
from the equations those constraints that lead to this superstrictness
by using the purely combinatorial concept of positionfree incidence structures.
People who are interested in this solution can find more details in the
paper References (2).
A little bit more talk ...
I. Shimshoni and J. Ponce propose a variation of Sugihara's approach. They define a system similar to Sugihara's but, unlike Sugihara, they do not eliminate constraints that lead to a superstrict set of equations, but explicitly introduce uncertainty in these constraints. A necessary condition for a line drawing to be the correct projection of a polyhedron is that this system admits a solution, which again can be tested using linear programming.
As far as our problem is concerned, the work of
several combinatorial geometers is often unnoticed by the robotics community.
In this sense, H. Crapo and W. Whiteley have been investigating the connection
between the realizability of linear scenes and the rigidity of planar bar
frameworks. An interesting result they have proved is that a line drawing
is consistent if and only if the planar bar framework it represents supports
a nonnull pattern of stresses on the bars. Hence, the realizability of
a drawing and the rigidity of a framework have been proved to be connected
problems.