Preprocessing chains for fast dihedral rotations is hard or even impossible. (Q1410594): Difference between revisions

This paper deals with the complexity of simulating the motion of polymers which are modeled by polygonal chains in three dimensions. Each edge of a given chain splits the polymer into two subchains. The motion is simulated by a dihedral rotation at a given edge which rotates one of the two subchains rigidly about the edge by a given angle. A feasible motion can cause no self-intersection of the chain. The problem is to determine if the motion is feasible. This paper proves that preprocessing a chain of \(n\) edges and answering \(n\) dihedral rotation queries is 3SUM-hard, and \(\Omega(n^2)\) preprocessing is required to achieve sublinear query time in the worst case. For dynamic queries, which also modify the chain if the requested dihedral rotation is feasible, this paper shows that answering \(n\) queries is by itself 3SUM-hard, and sublinear query time is impossible after any amount of preprocessing.