# Folding Every Point on a Polygon Boundary to a Point
## 1 Introduction  
Paper folding offers rich computational geometry problems with many real-world applications [1]. The topic, typically referred to as _computational origami_ or _mathematics of paper folding_[2, 3], studies both feasibility problems and also structural problems [4, 5, 6] with the aim to illuminate the connections between physical structures/problems and mathematical geometric objects (see, e.g., [7, 8]). As geometric construction using straightedge and compass offers elegant connections between algebra and geometry, paper folding, which can be seen as geometric construction with additional operations, may provide beautiful structural properties worth studying (e.g., see [2, 9]). [PERSON], [PERSON], [PERSON], [PERSON], and [PERSON] [4] previously considered two folding problems on a convex piece of paper \(P\). Given a query point \(p\) inside \(P\), their first problem, originally proposed by [PERSON] [10, 11, 12], called _points to a point_, is to find a region containing \(p\) bounded by creases after fold-and-unfold of each corner of \(P\) onto \(p\). Their second problem, called _lines to a line_, takes as an input a line \(\ell\) inside \(P\) and the goal is to find a region containing \(\ell\) bounded by creases after a fold-and-unfold of each side of \(P\) onto \(\ell\). Although these two problems share a similar structure, they find that the outcomes diverge. That is, the region in the first problem resembles a Voronoi cell [13] with the inner point and corners as seeds, while the region in the second problem relies on the straight skeleton of the piece of paper. We consider a variant of this folding problem in the same flavor, i.e., we are given a query point \(f\) inside \(P\) and we are interested in a region containing \(f\) bounded by creases after a fold-and-unfold of _every_ point on the boundary of the paper \(\delta P\) onto \(f\). We call this result region a _safe region_\(R\) since every point \(p\in R\) is safe from this folding procedure. Our contributions are an analysis of the shape of \(R\), an efficient algorithm for finding \(R\), and a complexity of the safe region with respect to any query point \(f\). Figure 0(a) shows a few creases after folding various points on polygon edge \(\overline{v_{2}v_{3}}\) onto point \(f\). The resulting safe region is shown in Figure 0(b). Figure 2 provides a comparison between point-to-point folding considered in [PERSON] et al. [4] (in Figure 1(a)) and our work (in Figure 1(b)). We first show that, although we fold infinitely many points on \(\delta P\), the result region \(R\) can be described finitely. It is a well-known result that a fold-and-unfold of multiple points from a line onto a point produces an envelope of a parabola. Thus, we consider each \"side\" of \(R\) as a parabolic arc instead of a traditional straight line segment. The analysis is presented in Section 2. Using the analysis of the properties of safe regions, we present a linear-time algorithm for finding the region \(R\), given a piece of paper \(P\) as a sorted list of \(n\) corners in counterclockwise order. Our algorithm works similarly to [PERSON]'s scan for a convex hull. That is, we consider adding one side of \(P\) as a parabola arc at a time, maintaining the loop invariant that regulates the region \(R\). During each iteration, we may destroy some of the previously added parabola arcs. The key insight is that the destroyed parabola arc must be the one that is closest to the newly added parabolic region. Thus, it allows us to amortize the cost of destroying, achieving a linear-time algorithm overall. Section 3 explains the algorithm in full detail. Finally, given any potential query point \(f\), we calculate the precise number of parabola arcs of the region \(R\). They turn out to be dependent on a set of inscribed circles, each of which is centered at a node of the straight skeleton of \(P\). We dedicate Section 4 to focus solely on this property. We hope that our problem will expand the richness of the family of fold-and-unfold origami problems.