Paper Abstract and Keywords |
Presentation |
2018-05-26 13:30
Strip flat folding with parallel oblique mountain-valley-assigned creases Hiro Ito (UEC), Chie Nara (Meiji Univ.), Izumi Shirahama (ECBEING), Mizuho Tomura (UEC) COMP2018-4 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
The flat foldability problem is a typical problem of origami mathematics, which asks whether or not a given paper with creases each of which has a mountain-valley assignment is flat foldable. This problem is know to be in NP-complete. However, some subproblems that can be solved in polynomial time have been known, and a representative example is that the paper is limited to a rectangular strip and the creases are perpendicular to the long axis of the strip, which is called one-dimensional flat folding problem with mountain-valley-assigned creases, and a linear time algorithm was given by Arkin et al. In this study, we tried to solve a problem that the angle formed by creases is equal to an arbitrary angle $¥theta$, which is not limited to $¥pi/2$, i.e., all creases are parallel. We call this problem strip flat folding problem with parallel oblique mountain-valley-assigned creases. As a remarkable feature when $¥theta$ is not equal to $¥pi/2$, if the distance between the two creases is apart in some value (a constant fixed by the width of the strip and $¥theta$), the strip can be separated into two, since they never affect each other. Therefore, in this case, we can solve the two problems independently. We present a linear-time algorithm for the strip flat folding problem with parallel oblique mountain-valley-assigned creases with an arbitrary angle $¥theta$ by applying the above separate operation to the algorithm of the one-dimensional flat folding problem with mountain-valley-assigned creases. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
origami / flat folding / algorithms / computational complexity / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 118, no. 68, COMP2018-4, pp. 63-70, May 2018. |
Paper # |
COMP2018-4 |
Date of Issue |
2018-05-18 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
COMP2018-4 |
Conference Information |
Committee |
COMP IPSJ-AL |
Conference Date |
2018-05-25 - 2018-05-26 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Nagoya Institute of Technology |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
COMP |
Conference Code |
2018-05-COMP-AL |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Strip flat folding with parallel oblique mountain-valley-assigned creases |
Sub Title (in English) |
|
Keyword(1) |
origami |
Keyword(2) |
flat folding |
Keyword(3) |
algorithms |
Keyword(4) |
computational complexity |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Hiro Ito |
1st Author's Affiliation |
The University of Electro-Communications (UEC) |
2nd Author's Name |
Chie Nara |
2nd Author's Affiliation |
Meiji University (Meiji Univ.) |
3rd Author's Name |
Izumi Shirahama |
3rd Author's Affiliation |
ECBEING (ECBEING) |
4th Author's Name |
Mizuho Tomura |
4th Author's Affiliation |
The University of Electro-Communications (UEC) |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-4 |
Date Time |
2018-05-26 13:30:00 |
Presentation Time |
30 minutes |
Registration for |
COMP |
Paper # |
COMP2018-4 |
Volume (vol) |
vol.118 |
Number (no) |
no.68 |
Page |
pp.63-70 |
#Pages |
8 |
Date of Issue |
2018-05-18 (COMP) |
|