Portalgons gone curvy

Abstract

In Löffler et al.’s paper, they define portalgon as a set of fragments together with a set of portals that “glue” fragment together along the portals. A portal e = (e^+, e^−) is a pair of directed, equal length edges of two, possibly the same, fragments of F. Let e^+ = uv and e^- = wz, where u, v vertices of the fragment containing e+ and w, z vertices of the fragment containing e^−. Let p^− be a point on e^− and p^+ on e^+. If there is a λ ∈ [0, 1] for which p^− = λu + (1 − λ)v, then p^+ = λw + (1 − λ)z. Furthermore, no edge can be part of multiple portals. In their paper, they explore shortest paths in these portalgons and find out that there is a way to represent the portalgon in such a way that the complexity of shortest paths is bounded. For this, they introduce happiness h; a portalgon is h-happy if any shortest path crosses every portal at most h times. The complexity of shortest paths in an h-happy portalgon is O(n + hm) where n is the number of vertices in the portalgon and m is the number of portals. Furthermore, they also discovered that every polyhedral surface has a representation as a portalgon where the happiness is constant. This means the complexity of shortest paths in the representation is O(n).[9] Note that an object with input size n has asymptotic upper bound O(f(n)) if and only if ∃N, c > 0, ∀n > N, g(n) ≤ c ・ f(n), where g(n) is the amount of components of the object that need constant space [7].

In this thesis, we expand their research into the realm of portalgons where the portals do not have to be linear anymore. Instead we are going to research fitting portals specifically, which are those portals where two corresponding edges are described by the same function and orientation. In other words, exactly those non-linear portals that fit together. We introduce the concepts of portal line segment (line segment between the start and end vertex of the portal) and obstacles (the boundary of the fragment, not the portal itself, intersecting with the portal line segment). In this thesis, we show that any portalgon P with n vertices, m straight portals (portals where its form is described by the portal line segment) and one fitting portal without any intersections between the portal and its portal line in an obstacle has an equivalent portalgon with O(n) vertices and straight portals. Then, it also follows that P has a representation as a portalgon where the happiness is constant. This means the complexity of shortest paths in the representation is O(n).