# Folding Every Point on a Polygon Boundary to a Point
## 3 The Algorithm
The counterclockwise ordering of parabolas ensures that \(p_{i}\) would affect two sequences of arcs, i.e., clockwisely,  
\[a_{k},a_{k-1},a_{k-2},\ldots,\]  
Figure 6: Three cases of adding parabola \(p_{i}\) to the partial safe region \(R_{i-1}\). (**a**) _Case 1_: \(p_{i}\) does not change the region. (**b**) _Case 2_: \(p_{i}\) clips the region. (**c**) _Case 3_: \(p_{i}\) eclipses some parabola. to be referred to as the _neighbors to the left_ of \(p_{i}\), and counterclockwise,  
\[a_{1},a_{2},a_{3},\ldots,\]  
to be referred to as the _neighbors to the right_ of \(p_{i}\),  
We first consider point \(q_{k1}=a_{k}r\) (which is also \(a_{1}.\ell\)). Lemma 4 below ensures that we are in Case 1 if \(q_{k1}\in H(p_{i})\). See Figure 7.  
Otherwise, some part of \(R_{i-1}\) is below parabola \(p_{i}\). We in turns consider the points:  
\[a_{k-1}.r,a_{k-2}.r,\ldots,\]  
from the neighbors to the left of \(p_{i}\) and find the largest index \(j\) such that \(a_{j}\cap H(p_{i})\
eq\emptyset\). In this case, the parabolas \(a_{k}.p,a_{k-1}.p,\ldots,a_{i+1}.p\) are eclipsed by \(p_{i}\). We also process the neighbors to the right of \(p_{i}\) similarly by finding the smallest index \(j^{\prime}\) such that \(a_{j^{\prime}}\cap H(p_{i})\
eq\emptyset\) together with the sequence of eclipsed arcs \(a_{1},a_{2},\ldots,a_{j^{\prime}-1}\). We note that it can be the case that \(j=j^{\prime}\) when only one arc survives \(p_{i}\) eclipsing. To construct \(R_{i}\), we discard eclipsed arcs, add a new arc \(a_{i}\) for \(p_{i}\), and compute the following:  
* The left intersection point \(a_{i}.\ell=a_{j}.r\), which is the intersection between \(p_{i}\) and \(a_{j}.p\);
* The right intersection point \(a_{i}.r=a_{j^{\prime}}.\ell\), which is the intersection between \(p_{i}\) and \(a_{j^{\prime}}.p\). Finally, we re-index the arcs in \(R_{i}\). We quickly remark that this procedure can be seen as a \"twin-headed\" Graham scan. The following lemmas show that this procedure is correct. Lemma 4: _If \(q_{k1}\in H(p_{i})\), then \(R_{i-1}\subseteq H(p_{i})\) and \(R_{i}=R_{i-1}\)._  
Proof: Since \(R_{i-1}\subseteq H(p_{1})\cap H(p_{k})\), our goal is to show that \(H(p_{1})\cap H(p_{k})\subseteq H(p_{i})\) in this case. Consider the intersection of \(p_{1}\) and \(p_{k}\). Recall that the two intersection points \(q_{k1}\) and \(q_{1k}\) partition both parabolas into their left arcs, central arcs, and right arcs. Let us call them \(a_{k}^{\ell},a_{k}^{\ell},a_{k}^{\ell}\) and \(a_{1}^{\ell},a_{1}^{\ell},a_{1}^{\ell}\). We now consider the intersection of \(p_{1}\) and \(p_{i}\). We show that \(q_{i1}\), the intersection point of \(p_{i}\) and \(p_{1}\), is on the left arc \(a_{1}^{\ell}\) of \(p_{1}\). To see this, we start by rotating the plane such that \(p_{i}\) is in the upright form. Then, we find a region \(r=H(p_{1})\cap H(p_{i})\). Since \(q_{k1}\in p_{1}\) and also \(q_{k1}\in H(p_{i})\), \(q_{k1}\) in on the boundary of \(H(p_{1})\cap H(p_{i})=r\). Again, since \(q_{k1}\in p_{1}\) and also on the boundary of \(r\), traversing from \(q_{k1}\) on the boundary of \(r\) clockwisely with respect to \(f\) would reach \(q_{i1}\), by definition of \(q_{i1}\), as claimed. Using the same argument, we can show that \(q_{ki}\) is in the right arc \(a_{k}^{\sigma}\) of \(p_{k}\). Using \(q_{i1}\) and \(q_{ki}\), we partition \(p_{i}\) into three arcs--\(a_{1},a_{2}\), and \(a_{3}\)--so that \(a_{1}\) is an unbounded curve with \(q_{i1}\) as its end point, \(a_{2}\) is a bounded part with \(q_{i1}\) and \(q_{ki}\) as their end points, and finally, \(a_{3}\) is an unbounded curve with \(q_{ki}\) as its end point (see Figure 7). Using the structure from Lemma 2, we know that \(a_{1}\cup a_{2}\) intersects \(p_{k}\) at only \(q_{ki}\in a_{k}^{\prime}\). Thus, \(p_{i}\) does not intersect \(a_{k}^{\varepsilon}\cup a_{k}^{\ell}\). \[R_{i}=\bigcap_{j=1}^{i}H(p_{j}),\]0 Proof of Lemma 4.