Scholarlink

We investigate a natural variant of the fold-and-cut problem. We are given a long paper strip P and a polygonal line, which consists of a sequence of line segments, drawn on P. We cut all the line segments by one complete straight cut after overlapping all of them by a sequence of simple foldings. Our goal is to minimize the number of simple foldings to do that. When the polygonal line satisfies certain geometric conditions, we can find a shortest sequence of simple foldings for the given polygonal line that consists of n line segments in \(O(\min \{n^3,n^2\log \frac{\ell _{\max }}{\ell _{\min }}\}\) ) time and \(O(n^2\) ) space, where \(\ell _{\max }\) and \(\ell _{\min }\) denote the maximum and minimum lengths of the line segments.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Optimal Simple Fold-and-Cut of a Polygonal Line

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Ryuhei Uehara

摘要

We investigate a natural variant of the fold-and-cut problem. We are given a long paper strip P and a polygonal line, which consists of a sequence of line segments, drawn on P. We cut all the line segments by one complete straight cut after overlapping all of them by a sequence of simple foldings. Our goal is to minimize the number of simple foldings to do that. When the polygonal line satisfies certain geometric conditions, we can find a shortest sequence of simple foldings for the given polygonal line that consists of n line segments in \(O(\min \{n^3,n^2\log \frac{\ell _{\max }}{\ell _{\min }}\}\) ) time and \(O(n^2\) ) space, where \(\ell _{\max }\) and \(\ell _{\min }\) denote the maximum and minimum lengths of the line segments.