Optimal Simple Fold-and-Cut of a Polygonal Line

• Item type: SIG Technical Reports(1)
• 公開日: 2023-05-03
• タイトル: Optimal Simple Fold-and-Cut of a Polygonal Line
• タイトル / 言語: en
• タイトル: Optimal Simple Fold-and-Cut of a Polygonal Line
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Japan Advanced Institute of Science and Technology
• 著者名: Ryuhei, Uehara
• 著者名(英): Ryuhei, Uehara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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 some 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(n3) time and O(n2) space.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 some 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(n3) time and O(n2) space.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2023-AL-193, 号 13, p. 1-4, 発行日 2023-05-03
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会