2023/05/02 by Phetmak, Nattawut, Fakcharoenphol, Jittat
#68U05 #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2305.01467
We consider a problem in computational origami. Given a piece of paper as a convex polygon P and a point f located within, fold every point on a boundary of P to f and compute a region that is safe from folding, i.e., the region with no creases. This problem is an extended version of a problem by Akitaya, Ballinger, Demaine, Hull, and Schmidt~[CCCG'21] that only folds corners of the polygon. To find the region, we prove structural properties of intersections of parabola-bounded regions and use them to devise a linear-time algorithm. We also prove a structural result regarding the complexity of the safe region as a variable of the location of point f, i.e., the number of arcs of the safe region can be determined using the straight skeleton of the polygon P.