Analysing spatial realizability of line drawings through edge-concurrence tests

Abstract

Proves that the realizability of a line drawing without occluding segments can be verified by checking the concurrence of groups of three lines to a single point. These lines are either those supporting segments in the drawing or new ones added during the test itself. Although this result was essentially already established by Whiteley , the presented approach uses the concept of delta-star reductions to obtain all possible spatial realizations and consistent edge-labellings (convex or concave) of a given drawing. As opposed to well-known algebraic approaches, which require a Waltz filtering preprocessing step before proceeding to the global geometric test the approach presented is based on geometrically interpretable projective conditions which allows an easy localization of the source of eventual inconsistencies.