A New Dynamic Programming Algorithm for Orthogonal Ruler Folding Problem in d-Dimensional Space

摘要

A chain or n-link is a sequence of n links whose lengths are fixed joined together from their endpoints, free to turn about their endpoints, which act as joints. "Ruler Folding Problem", which is NP-Complete is to find the minimum length of the folded chain in one dimensional space. The best result for ruler folding problem is reported by Hopcroft et al. in one dimensional space which requires O(nL~2) time complexity, where L is length of the longest link in the chain and links have integer value lengths. We propose a dynamic programming approach to fold a given chain whose links have integer lengths in a minimum length in O(nL) time and space. We show that by generalizing the algorithm it can be used in d-dimensional space for orthogonal ruler folding problem such that it requires O(2~dndL~d) time using O(2~dndL~d) space.