Abstract: This paper answers the following question: Given an ``erector set'' linkage, a connected set of fixed-length links, what is the minimal e needed to adjust the edge lengths so that the vertices of the linkage can be placed on integer lattice points? Each edge length is allowed to change by at most e. Angles are not fixed, but collinearity must be preserved (although the introduction of new collinearities is allowed). We show that the question of determining whether a linkage can be embedded on the integer lattice is strongly NP-complete. Indeed, we show that even with e = 0 (under which the problem becomes ``Can this linkage be embedded?''), the problem remains strongly NP-complete. However for some applications, it is reasonable to assume that lengths of the links and the number of ``co-incident'' cycles are bounded (two cycles are co-incident if they share an edge). We show that under these bounding assumptions, there is a polynomial time solution to the problem.
Recent Publications of Neil Immerman