Make your own free website on Tripod.com
  

"The individual mathematician feels free to define his
notions and set up his axioms as he pleases. But the
question is: will he get his fellow mathematician interested
in the constructs of his imagination ?"

Hermann Weyl, 1951 [66].


 

Now let's take a look at Sugihara's famous assumptions on line drawing interpretation problems:

1.  Assumptions on Objects:

  • Assumption O1:  Polyhedrons are bounded and homogeneously three-dimentional.
  • Assumption O2:  Polyhedrons are topologically equivalent to a ball
  • Assumption O3:  Polyhedrons are convex.
  • Assumption O4:  Polyhedrons are trihedral.
  • Assumption O5:  Polyhedrons are rectangular.
  • A vertex is called rectangular if all the faces meeting at the vertex are mutually perpendicular.
    A polyhedron is called rectangular if all the vertices are rectangular.
    Note that O5 does not imply O4. The following figure is an example that is rectangular but not trihedral, six faces meet at the central vertex.

    Figure:  Polyhedron that is rectangular but not trihedral.




    2.  Assumptions on Points of View:

  • Assumption W1:  No face of a polyhedron is coplanar with the view point.
  • It implies that every face of a polyhedron corresponds to some region of the picture with nonzero area.
  • Assumption W2:  No pair of edges of a polyhedron is coplanar with the view point unless the two edges are collinear in the space.
  • Assumption W3:  No pair of a vertex and an edge of a polyhedron is coplanar with the view point unless the vertex is one of the two terminal points of the edge.
  • Assumption W4:  No pair of vertices of a polyhedron is collinear with the view point.

  • Figure:  An object, the view point, and the picture.
    Note the assumption W2 implies W1, and W3 implies both W2 and W4(hence, W1 too). These types of assumptions are often called nonaccidentalness assumption. So for that Truncated Pyramid Question we mentioned in the introduction part, the situation showed in Figure 1(c) violates assumptions W1, W2, W3, and W4; consequently, if we choose at least one of these four assumptions, we can avoid the tricky answer.


    3.  Assumptions on Drawing Rules:

    This assumption seems less realistic, but more fundamental for study of the mathematical structure of line drawings.



    We have listed many assumptions which are necessary and useful to make the realizability problem senseful. Usually only some subset of these assumption set are adopted. Different subsets define different problems. In this project, the following type of realizability problems are considered:

    1.  Problem with Assumption(PA)
        Definition:  given a line drawings and a set of assumptions, judge whether a polyhedron is realizable from the line drawings.


      2.  Problem with the View point(PV)

         
        Definition:  given a line drawings and the view point, judge whether a polyhedron is realizable from the line drawings with respect to the view point.


      3.  Problem with additional Knowledge(PK)
       

        Definition:  given a line drawing and some additional knowledge about the structure of a polyhedron, judge whether a polyhedron with the given structure is realizable from the line drawing.
        What's additional knowledge ? A typical knowledge of such knowledge is given by labels assigned to lines, as will be seen in the page Labeling Algorithm. A problem in which additional knowledge about the structure of the object is not given is usually decomposed into a set of subproblems of the type PK.


      4.  Problem requiring Flexibility(PF)
       

        Definition: given a line drawing, judge whether it can be regarded(in some practical sense) as a picture of a polyhedron.
        This problem arised from whether the realizability is judge strictly or flexibly. As we have seen, the line drawing in that Truncated Pyramid Question is not a correct projection of a truncated pyramid. This kind of incorrectness, however, usually arises in practical data: digitization errors are inevitable when picture data are given to a computer. So, the realizability should be judged "flexibly" in the sense that pictures are regarded as being "practically correct" if incorrectness is only dut to small errors in vertex positions.


    In this way we shall distinguish the problem types by thr symbols PA, PV, PK, and PF. We shall use the symbols also in combination. For example, PAV stands for the type of a problem in which a set of assumptions and the view point are given. PAVK stands for the type of a problem in which a set of assumptions, the view point, and additional knowledge about the structure of the object are given, etc. Obviously a problem of the type PAK is a subproblem of the corresponding problem of the type PA. Here we are going to talk about a method for decomposing a type-PA problem into type-PAK subproblems. The method is just the famous Labeling Algorithm.
     
     

    IntroductionHomeLabeling Scheme