# Folding Every Point on a Polygon Boundary to a Point
## 3 The Algorithm  
Our algorithm for finding a safe region works similarly to [PERSON]'s scan [15] for convex hull. We briefly described the algorithm as a pseudocode in Algorithm 1. Later in this section, we explain the algorithm and prove its correctness. ```
functionSafeRegion(\(P:\textsc{Polygon},f:\textsc{Point}\)) \([e_{1},e_{2},e_{3},\ldots,e_{n}]\gets E(P)\) \(p_{1}\leftarrow\textsc{Parabola}(f,e_{1})\) \(p_{2}\leftarrow\textsc{Parabola}(f,e_{2})\) \(q_{12}\leftarrow\textsc{InnerIntersection}(p_{1},p_{2})\) \(q_{21}\leftarrow\textsc{InnerIntersection}(p_{2},p_{1})\) \(R\leftarrow\textsc{DoublyLinkedist}(\textsc{Arc}(p_{1},q_{21},q_{12}), \textsc{Arc}(p_{2},q_{12},q_{21}))\) for\(i\in[3,4,5,\ldots,n]\)do \(p_{i}\leftarrow\textsc{Parabola}(f,e_{i})\) \((p_{H},\ell_{H},r_{H})\leftarrow\textsc{Head}(R)\) \((p_{T},\ell_{T},r_{T})\leftarrow\textsc{Tail}(R)\) \(q_{Ti}\leftarrow\textsc{InnerIntersection}(p_{T},p_{i})\) \(q_{iH}\leftarrow\textsc{InnerIntersection}(p_{i},p_{H})\) if\(q_{iH}\in\textsc{LeftArc}(p_{H},\ell_{H})\wedge q_{Ti}\in\textsc{ RightArc}(p_{T},r_{T})\)then continue// skip this iteration while\(q_{iH}\in\textsc{RightArc}(p_{H},r_{H})\)do \(R\leftarrow\textsc{RemoveHead}(R)\) \((p_{H}\_,r_{H})\leftarrow\textsc{Head}(R)\) \(q_{iH}\leftarrow\textsc{InnerIntersection}(p_{i},p_{H})\) while\(q_{Ti}\in\textsc{LeftArc}(p_{T},\ell_{T})\)do \(R\leftarrow\textsc{RemoveTail}(R)\) \((p_{T},\ell_{T},\r_{-})\leftarrow\textsc{Tail}(R)\) \(q_{Ti}\leftarrow\textsc{InnerIntersection}(p_{T},p_{i})\) \(R\leftarrow\textsc{UpdateHead}(R,\textsc{Arc}(p_{H},q_{iH},r_{iH}))\) \(R\leftarrow\textsc{UpdateTail}(R,\textsc{Arc}(p_{T},\ell_{T},q_{TI}))\) \(R\leftarrow\textsc{AppendTail}(R,\textsc{Arc}(p_{i},q_{TI},q_{iH}))\) return\(R\)
```  
**Algorithm 1**Our algorithm for finding the safe region. Algorithm 1 uses the following subroutines. Subroutine \(\textsc{Parabola}(f,e)\) creates a representation of a parabola with \(f\) as its focus and a line extension of edge \(e\) as its directrix. Subroutine \(\textsc{InnerIntersection}(p_{i},p_{j})\) computes the intersection point \(q_{ij}\) of parabola \(p_{i}\) and \(p_{j}\); we recall that from Lemma 2, there are two intersection points and this subroutine returns the \"inner\" one, i.e., \(q_{ij}\), not \(q_{ji}\). Since our goal is to find a safe region,  
\[R=\bigcap_{i=1}^{n}H(p_{i}),\]  
Algorithm 1 iterates over parabola \(p_{i}\) producing a partial solution \(R_{i}\) such that:  
\[R_{i}=\bigcap_{j=1}^{i}H(p_{j}),\]  
i.e., \(R_{i}\) is the safe region for the first \(i\) parabolas. We maintain \(R_{i}\) as a cyclic list of parabola arcs:  
\[a_{1},a_{2},\ldots,a_{k},\]  
where each arc \(a_{j}\) is a 3-tuple \((p,\ell,r)\) which keeps a reference to the parabola \(a_{j}.p\), its left endpoint \(a_{j}.\ell\), and its right endpoint \(a_{j}.r\). We note that with this representation, \(a_{j}.r=a_{j+1}.\ell\) for \(1\leq j<k\), and \(a_{k}.r=a_{1}.\ell\). We also note that, using the notation defined in Section 2.2, \(a_{j}.r\) is \(q_{j(j+1)}\) and \(a_{j}.\ell\) is \(q_{(j-1)}\). Initially, we start with \(R_{2}=H(p_{1})\cap H(p_{2})\). We encode the partial safe region as an ordered list of arcs, \(A(R_{2})=[a_{1},a_{2}]\), where:  
\[a_{1} =(p_{1},q_{21},q_{12})\] \[a_{2} =(p_{2},q_{12},q_{21})\]  
For each iteration \(i>2\), we consider adding \(H(p_{i})\) to \(R_{i-1}\) to produce \(R_{i}=R_{i-1}\cap H(p_{i})\). There are three cases:  
* _Case 1_: \(p_{i}\) does not change the region, i.e., \(R_{i-1}\cap H(p_{i})=R_{i-1}\) and we can discard \(p_{i}\);
* _Case 2_: \(p_{i}\) clips the region, i.e., all parabola arcs in \(R_{i-1}\) remain on the boundary of \(R_{i-1}\cap H(p_{i})\); or
* _Case 3_: \(p_{i}\)_eclipses_ other parabolas in the region, i.e., some parabola arc is entirely outside \(R_{i-1}\cap H(p_{i})\). Figure 6 illustrates these three cases. The safe regions \(R_{i-1}\) are shown with additional parabolas \(p_{i}\) with \(e_{i}\) as their directrices. To distinguish between these cases, our basic procedure is to test if a point lies in \(H(p_{i})\).