UNI-MB - logo
UMNIK - logo
 
E-viri
Celotno besedilo
Recenzirano Odprti dostop
  • Folding Every Point on a Po...
    Phetmak, Nattawut; Fakcharoenphol, Jittat

    Algorithms, 06/2023, Letnik: 16, Številka: 6
    Journal Article

    We consider a problem in computational origami. Given a piece of paper as a convex polygon P and a point f located within, we 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 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.