Abstract We formulate a novel characterization of a family of invertible maps between two-dimensional domains. Our work follows two classic results: The Radó-Kneser-Choquet (RKC) theorem, which establishes the invertibility of harmonic maps into a convex planer domain; and Tutte's embedding theorem for planar graphs -RKC's discrete counterpartwhich proves the invertibility of piecewise linear maps of triangulated domains satisfying a discrete-harmonic principle, into a convex planar polygon. In both theorems, the convexity of the target domain is essential for ensuring invertibility. We extend these characterizations, in both the continuous and discrete cases, by replacing convexity with a less restrictive condition. In the continuous case, Alessandrini and Nesi provide a characterization of invertible harmonic maps into non-convex domains with a smooth boundary by adding additional conditions on orientation preservation along the boundary. We extend their results by defining a condition on the normal derivatives along the boundary, which we call the cone condition; this condition is tractable and geometrically intuitive, encoding a weak notion of local invertibility. The cone condition enables us to extend Alessandrini and Nesi to the case of harmonic maps into non-convex domains with a piecewise-smooth boundary. In the discrete case, we use an analog of the cone condition to characterize invertible discrete-harmonic piecewise-linear maps of triangulations. This gives an analog of our continuous results and characterizes invertible discrete-harmonic maps in terms of the orientation of triangles incident on the boundary. Introduction This paper studies invertible maps, i.e., maps for which an inverse mapping exists. These maps are also sometimes called 1-to-1 maps, since they define a 1-to-1 correspondence between domains. This correspondence is crucial in many fields, for instance in enabling the study of variations of properties across a collection of objects: in the context of computational anatomy, considering different specimens of an organ and studying the variation of corresponding regions aids the classification of the specimen as healthy or unhealthy. Similarly, in the context of evolutionary biology, variation across a collection is instrumental in the construction of phylogenetic trees describing how species evolve. Introduction Mathematicians have long tried to find families of maps that are guaranteed to be invertible, i.e., prove that if some criteria hold for a map, it is invertible. This is also the focus of our work. Namely, this paper concerns harmonic maps between two-dimensional domains (little is known regarding invertibility of harmonic maps into high-dimensional domains, and Figure 1 . Planar harmonic maps into non-convex domains. Left panel shows a surface harmonically mapped into two different non-convex domains. Red arrows depict the normal gradients along the boundary; these can be thought of as the "forces" exerted by a system of springs or a membrane along the fixed boundary. In the top row, the forces along the boundary all point inwards, thus satisfying the cone condition we propose in this work which guarantees the resulting harmonic embedding is invertible. The second row shows a noninvertible harmonic mapping into a non-convex domain; in this case, "forces" point outwards as the spring/membrane is pulled out of the target domain, causing self-overlaps. The right panel shows that the exact same result holds for a discrete harmonic embedding of a triangulated surface. Introduction existing counterexamples indicate that the higher-dimensional case requires much more intricate assumptions). We consider two analogous families of maps for two separate cases -the continuous case, in which one continuous domain is mapped into another continuous domain; and the discrete case, in which a triangulated surface is mapped into a polygonal domain. Introduction One of the largest known families of invertible harmonic maps is characterized by the celebrated Radó-Kneser-Choquet (RKC) theorem [1, 2, 3, 4] . RKC considers harmonic maps of planar disks into other planar domains (i.e., maps whose coordinate functions are solution of Laplace's equation). RKC states that given a homeomorphism (i.e., a continuous map with a continuous inverse) of the unit circle onto a simple closed curve bounding a convex region, extending it harmonically to the interior produces a homeomorphism of the unit disk onto the interior of the curve. Though the constraint that the source domain is a disk may appear overly restrictive, taken in conjunction with the Riemann Mapping Theorem, RKC implies that a harmonic map of any compact Riemann surface with disk topology into a convex domain, such that the map between the one-dimensional boundaries is a homeomorphism, is itself a homeomorphism of the two-dimensional domains. Introduction In the discrete case, a closely-related characterization of invertible maps is derived from Tutte's work on planar embeddings of graphs [5] . Tutte considered planar 3-connected graphs and their barycentric embeddings, in which the position of each vertex is set to the average of its neighbors' positions. When the outer face is a convex polygon, Tutte proved that the edges of such a barycentric embedding, realized as straight lines, do not cross. Introduction Maps of triangulations have been further studied in [6, 7, 8] , which consider discrete-harmonic embeddings of triangulated surfaces with disk topology. As in Tutte's embedding, maps are specified by prescribing the position of vertices within the target domain, and are extended to the interior of triangles through linear interpolation. These works show that if the image of the boundary of a triangulation is a convex polygon, then the interpolated map is a homeomorphism. This property of discrete-harmonic maps, along with their computational tractability (via solving a single sparse system of linear equations), accounts for their broad applicability in computer graphics, including meshing, shape analysis, parameterization, and texture mapping [9, 10, 11, 12, 13, 14, 15, 16, 17] . Introduction Approach. In this paper, we extend the characterization of invertible (planar) harmonic maps. To this end, we consider harmonic and discrete-harmonic maps into non-convex regions, and study conditions under which such maps are homeomorphisms. This enables the definition of correspondences while providing more degrees of freedom for optimizing the quality of the map (e.g. the extent to which the map distorts the notion of lengths, angles, areas). Introduction One cannot simply omit the convexity requirement: in both the continuous (RKC) and discrete (Tutte) theorems, convexity plays a crucial role. For example, in the continuous case, it is known (Choquet [4] ) that for any non-convex region bounded by a simple curve, there exists some homeomorphism from the unit circle to the boundary curve for which the harmonic extension to the unit disk fails to be a homeomorphism [4, 18] . Figure 1 illustrates harmonic and discrete-harmonic maps into non-convex domains. Introduction Hence, our work is driven by the following question: is there a property sufficient to guarantee injectivity, which is trivially satisfied in the case of convex boundaries, but can also be satisfied in non-convex cases? As we will show, the answer is affirmative and the conditions are tractable. Introduction To give an informal intuition for our condition, imagine a system of springs with a fixed boundary; once the system reaches equilibrium, interior forces cancel out (this is the physical interpretation of the harmonicity condition), except along the boundary where the forces acting on the boundary are balanced by external forces holding the boundary in place (the Dirichlet boundary conditions). At any point along the boundary, if the interior forces point inwards, the membrane is pulled inwards and locally should be in the interior of the target domain. If, on the other hand, the internal forces point outward, the membrane is pulled out of the target domain, and folds over the boundary to spill out. See Figure 1 for an illustration. Introduction We formalize this intuition in terms of normal derivatives and prove that the condition requiring forces to point inwards (which is trivially satisfied for convex target domains) is sufficient to prove invertibility, independently of the target boundary's shape. Introduction In the continuous case, we build on results by Alessandrini and Nesi [18, 19] . They show that a sufficient and necessary condition for a harmonic map to be a homeomorphism is that it is a local homeomorphism along the boundary. If the boundary map is differentiable, they prove that a harmonic map is a homeomorphism if and only if it is orientation-preserving along the boundary. We extend their result to the continuous case of a boundary curve admitting a finite number of isolated singularities. To that end, we replace their orientation condition and define a simple geometric condition on the "forces" at the non-smooth points of the boundary, which we call the cone condition. We then prove that the cone condition characterizes homeomorphic harmonic maps. Figure 2 . An overview of the results discussed in this paper, illustrating the types of target domains (blue) and boundary conditions (pink) involved in characterizing invertible harmonic maps in the continuous setting (top) and the discrete one (bottom). If the target domain's boundary is convex, the RKC theorem (a) and Tutte embedding theorem (d) provide a guarantee of invertibility. Introduction In case the boundary is non-convex, Alessandrini-Nesi characterize invertibility in terms of the map's orientation along the boundary (b). We introduce a simple cone condition at non-smooth points of the boundary allowing us to extend their result to the case of a piecewise smooth boundary (c). A discrete version of the cone condition enables the characterization of invertible piecewise-linear maps in the discrete case (f); lastly, we use this result to prove a discrete analog of the Alessandrini-Nesi theorem, characterizing invertibility in terms of the orientation of triangles adjacent to the boundary (e). Introduction In the discrete case, discrete-harmonic maps into non-convex domains have been characterized in Gortler et al. [8] . We provide an alternative characterization in terms of a discrete analog of the cone condition, which, as in the continuous case, is an intuitive geometric condition along the boundary. We prove that it suffices to consider the discrete cone condition at the "non-convex boundary" (i.e., reflex) vertices to characterize discrete-harmonic intersection-free embeddings of triangulations. These, in turn, induce piecewise-linear homeomorphisms. Finally, we derive a discrete analog of the result by Alessandrini and Nesi, characterizing discrete-harmonic maps in terms of the orientation of triangles adjacent to the boundary. Introduction The rest of the paper is organized as follows: Section 2 is concerned with harmonic maps in the continuous case and Section 3 with discrete-harmonic maps in the case of triangulations. The analogy between the conditions and results for the continuous and discrete statements is illustrated in Figure 2 Introduction Note that φ = (φ 1 , φ 2 ) has two coordinates, as does γ = (γ 1 , γ 2 ); hence the notation of (1) should be understood as being applied to each coordinate separately. When needed, we shall use the polar coordinates defined by (ν, θ) → (1 − ν)e iθ , with −π ≤ θ ≤ π and 0 ≤ ν ≤ 1. Note that, as opposed to the classic definition of polar coordinates, in our definition ν = 0 corresponds to the boundary of the disc, and ν = 1 corresponds to its center, (0, 0). This slight variation will simplify the subsequent equations. Figure 3 depicts the problem setup and notations. One of the most well-known results on injectivity of harmonic mappings is due to Radó, Kneser and Choquet (RKC), who prove that if Ω is convex then the harmonic extension of γ : ∂B → ∂Ω is a homeomorphism [1, 2, 3, 4] : Introduction The RKC theorem is known to be sharp, in the following sense: Introduction Theorem 2 (Choquet [4] ). If Ω is not convex, there exists a homeomorphism γ : ∂B → ∂Ω such that the harmonic extension φ is not a homeomorphism. Introduction An alternative proof of Theorem 2, with a more explicit construction, was recently given by Alessandrini and Nesi [18] . We provide an even simpler proof in Section A.2. Introduction On the other hand, even when ∂Ω encloses a non-convex domain, there always exist boundary maps whose harmonic extension, i.e., the solution to (1) φ, is a homeomorphism. In fact, for any simple closed curve Γ = ∂Ω, there always exists a specific choice of the boundary map γ : ∂B → ∂Ω that yields a homeomorphic φ: one such boundary map can be constructed by considering the Riemann mapping [20, p. 420 ] from the interior of the unit disk to the interior of the domain enclosed by ∂Ω, which is a harmonic homeomorphism. Then, by Caratheodory's theorem [20, p. 445] , there is a continuous extension to the boundary, yielding the desired γ. Introduction The following theorem, by Alessandrini and Nesi, states specific conditions that ensure that the harmonic extension φ is injective even when the target boundary is non-convex, assuming the boundary map is C 1 . Introduction Theorem 3 (Alessandrini-Nesi [18, 19] ). Let γ : ∂B → ∂Ω be an orientation preserving diffeomorphism of class C 1 onto a simple closed curve Γ = ∂Ω and let φ ∈ C 2 (B, R 2 ) ∩ C 1 (B, R 2 ) be a solution of (1). Introduction The mapping φ is a diffeomorphism of B onto Ω if and only if det Dφ > 0 everywhere on ∂B. 2.2. Harmonic extensions to non-smooth boundary maps. As a step towards the discrete case, we consider also mappings γ : ∂B → Γ that are only piecewise differentiable, and aim to formulate a criterion for guaranteeing the harmonic extension φ is a homeomorphism. Towards that end, we draw inspiration from Alessandrini and Nesi (Theorem 3), but replace their determinant condition with a weaker condition, expressed in terms of one-sided derivatives, thus extending their result to the case of a piecewise-smooth boundary. We will assume that the derivative γ = dγ/dθ of the boundary map exists and is strictly bounded away from zero in all but finitely many points. We denote the set of boundary points in which the derivative does not exist as S ⊂ ∂B. We will also assume that the normal derivative ∂φ/∂ν of the harmonic extension is defined at all points in ∂B, does not vanish, and is continuous on ∂B. For points e iθ ∈ S ⊂ ∂B where the derivative γ = dγ/dθ does not exist, we assume that the one-sided derivatives γ + and γ − exist and do not vanish. 2.2. For every boundary point e iθ ∈ ∂B we define a cone C θ as the set resulting from the intersection of the two "inward-pointing" half-planes supporting the vectors of the one-sided derivatives γ + and γ − ; see figure 4 for an illustration in which the cone is colored in dark-grey. 2.2. Formally, suppose γ is an orientation-preserving homeomorphism of the boundary, i.e., it traverses Γ in the counter-clockwise direction. The open cone C θ at point e iθ is defined as 2.2. where z ⊥ denotes the π/2 clockwise rotation of z. Figure 4 . The cone condition: the normal derivative is contained within the intersection of the "inward-pointing" half-planes supporting the one-sided derivatives. 2.2. Note that for a differentiable boundary point, i.e., e iθ / ∈ S, the two one-sided derivatives are equal, γ + e iθ = γ − e iθ . Thus, in this case, C θ is simply a half-space. On the other hand, if the one-sided derivative point in opposite directions (in which case the opening angle is 0 or 2π) then the cone C θ is empty. Lastly, note that since C θ is an intersection of two half-spaces, it has an opening angle of at most π, regardless of the opening angle of ∂Ω at that point (see inset). 2.2. Given a map φ : B → Ω we say it satisfies the cone condition at e iθ ∈ ∂B if the following equation holds 2.2. Intuitively, the cone condition requires that the derivative of the harmonic map in the normal direction is contained within the cone. It turns out that this simple condition can be used to formulate a theorem similar to that of Alessandrini-Nesi's, in which the cone condition replaces the determinant condition, ensuring that the resulting map φ is a homeomorphism into Ω. Furthermore, we will show that, as the cone condition permits the boundary map γ to have derivative discontinuities, it extends Alessandrini-Nesi's result to harmonic maps into domains with a non-smooth boundary. More precisely, Theorem 4. Assume that γ : ∂B → Γ is an orientation preserving homeomorphism onto a simple closed curve Γ = ∂Ω that is C 1 at all but a finite set of points S ⊂ ∂B. Also assume that γ does not vanish on ∂B \ S, and that for each point in S the one-sided derivatives γ + and γ − exist, do not vanish and equal the limit of γ on the corresponding side. 2.2. Let (1) . Further assume that everywhere on ∂B, the normal derivative ∂φ/∂ν exists, is continuous and does not vanish. The map φ is a homeomorphism of B onto Ω if and only if it satisfies the cone condition (3) everywhere on ∂B. 2.2. Proof. A main ingredient of our proof is another theorem by Alessandrini and Nesi: φ ν ∂φ ∂ν Figure 5 . Local monotonicity: The cone condition ∂φ ∂ν ∈ C θ implies that the boundary map γ : ∂B → Γ is locally monotone in the direction perpendicular to the normal derivative ∂φ ∂ν . 2.2. be the solution of (1). The mapping φ is a homeomorphism of B onto Ω if and only if, for every point e iθ ∈ ∂B, the mapping φ is a local homeomorphism at e iθ (i.e., there exists a neighborhood of e iθ where φ is injective). 2.2. One direction of the proof ("if") can thus be obtained by showing that for every boundary point e iθ ∈ ∂B, the cone condition implies that φ is a local homeomorphism at e iθ . 2.2. The cone condition ∂φ ∂ν e iθ ∈ C θ implies that 2.2. at the boundary point e iθ ∈ ∂B. For differentiable boundary points e iθ ∈ ∂B \ S, (4) along with continuity imply that the normal and tangential derivatives are linearly independent in a neighborhood of e iθ . Hence, the differential of the map Dφ is invertible and, by the inverse function theorem, there exists a neighbourhood of e iθ in which φ is a local homeomorphism. 2.2. For a point e iθ ∈ S ⊂ ∂B, where the derivative is discontinuous, the argument is more subtle, but follows a similar idea. In this case, the cone condition (4) implies that the boundary map γ : ∂B → Γ ⊂ R 2 is locally monotone in the direction perpendicular to the normal derivative at e iθ ; see Figure 5 for an illustration. Namely, there exists a δ-neighborhood of θ and c > 0 such that for all 2.2. (With this notation we assume, without loss of generality, that |θ| is sufficiently far away from π.) One can leverage this monotonicity to establish a uniform bound on the angle between the normal and tangential derivatives of the harmonic extension, ∂φ/∂ν and ∂φ/∂θ, in a neighborhood of e iθ . Thus, the cone condition implies that, in a sufficiently small neighborhood of e iθ , the normal and tangential derivatives are well-behaved and define a consistent local coordinate system. More precisely, we prove (following this line of reasoning) in Appendix A.1 the following Lemma: 2.2. Under the conditions of Theorem 4, the harmonic extension φ is a local homeomorphism around all boundary points e iθ , −π ≤ θ ≤ π. 2.2. Thus we see that if the cone condition holds for all boundary points ∂B then (since φ is a local-homeomorphism at all points on ∂B) Theorem 5 implies φ is a homeomorphism of B onto Ω. 2.2. For the other direction ("only if"), if e iθ ∈ ∂B does not satisfy the cone condition then the inner product in (4) is either zero or negative, for at least one of the one-sided derivatives; without loss generality we shall assume the cone condition is violated for ∂ + φ/∂θ. If (4) vanishes then ∂φ/∂ν and ∂ + φ/∂θ are colinear, in which case Theorem 5 implies that φ is not a homeomorphism. Otherwise, if (4) is negative, then a neighborhood of e iθ ∈ ∂B in B is mapped outside of Ω, as well implying that φ is not a homeomorphism. Discrete-Harmonic Mappings In this section we discuss discrete analogs of the results presented in Section 2. Preliminaries. Triangulations. We consider a triangulation T = (V, E, F ) over a finite set of vertices V = {v 1 , . . . , v n } defined by a set of faces (triangles) Preliminaries. and a corresponding set of edges Preliminaries. We think of the set of faces F as (non-ordered) subsets of vertex triplets. The edges E are ordered pairs of vertices, corresponding to the directed edges connecting the vertices of each face. Preliminaries. A boundary edge of the triangulation is an edge associated with only a single triangle; that is, Preliminaries. The boundary of the triangulation is the union of all boundary edges. We say that a vertex is a boundary vertex if it belongs to a boundary edge and an interior vertex otherwise. We say that a triangulation is 3-connected if it remains connected after the removal of any two vertices and their incident edges. Preliminaries. A drawing of a given triangulation T is a mapping of each vertex v i ∈ V to a distinct point x i ∈ R 2 of the plane and of each edge (v i , v j ) ∈ E to a simple curve with endpoints x i and x j . A drawing is intersection-free if its edges do not intersect except, possibly, at common endpoints. We say that a drawing is proper if its faces coincide with the faces of T and the edges of its external (unbounded) face coincide with the boundary edges of T . A triangulation T has disk topology if its boundary is a cycle and it has a proper intersection-free drawing. See Figure 6 for illustrations. Preliminaries. Lastly, a straight-line drawing is a drawing in which each edge is realized by a straight line segment connecting its endpoints; we use a pair (x, T ) to denote the straight-line drawing c) is an intersection-free drawing of a triangulation that does not have disk topology (note that the diagonal edge is associated with three triangles). determined by an embedding x = (x 1 , ..., x n ) ∈ R 2×n . If (x, T ) is a proper intersection-free straight-line drawing we denote by Ω (x,T ) ⊂ R 2 the simple polygonal domain enclosed by the boundary of the the straight-line drawing (x, T ). See Figure 7 for illustrations. Discrete-harmonic embeddings. Moving forward, we assume that we are given a proper intersectionfree straight-line drawing (x, T ) of a 3-connected triangulation T with disk topology and vertex coordinates x = (x 1 , ..., x n ) ∈ R 2×n . Let y = (y 1 , ..., y n ) ∈ R 2×n be some assignment of vertex coordinates and let w = (w ij ) be weights associated with the directed edges (v i , v j ) ∈ E of T ; note that we do not assume that w ij = w ji . We define the discrete Laplace operator L w (y, T ) : V → R 2 with weights w with respect to the straight-line drawing (y, T ) by Preliminaries. is the weighted sum of the edges incident to the i'th vertex in the straight-line drawing (y, T ) of the triangulation T . Let P ⊂ R 2 a simple polygonal domain with number of vertices corresponding to the boundary of T . We say that an assignment y = (y 1 , ..., y n ) ∈ R 2×n of vertex coordinates is discrete-harmonic into P with weights w = (w ij ) if it satisfies (7) L w (y, T ) = 0 for all interior vertices and maps the boundary vertices of T onto the boundary of P. Preliminaries. For an assignment y = (y 1 , ..., y n ) of vertex coordinates, we denote by φ (x,T )→(y,T ) : Ω (x,T ) → R 2 the continuous piecewise-linear map defined by linearly interpolating the vertex assignments φ(x i ) → y i over each triangle. Preliminaries. 3.2. The Convex Case. Discrete-harmonic embeddings are often discussed in the case that P is convex, following a classic result originating in the work of Tutte [5] : Preliminaries. Theorem 7. Let y = (y 1 , ..., y n ) ∈ R 2×n be a discrete-harmonic embedding (7) into a simple polygonal domain P. If P is convex then for any positive weights w ij > 0 the straight-line drawing (y, T ) is intersection-free. Moreover, the piecewise-linear map φ (x,T )→(y,T ) induced by y is a homeomorphism of Ω (x,T ) onto P. Preliminaries. The result proved in [5] addresses the intersection-free realization of a more general class of planar 3-connected graphs via the solution of equations similar to (7) with uniform weights. The case of arbitrary positive weights is similar, and is discussed in the context of triangular meshes in [8] . Floater [7] shows that the discrete-harmonic piecewise-linear map φ (x,T )→(y,T ) is a homeomorphism. This result is often seen as a discrete analog of the Rado-Kneser-Choquet Theorem. 3.3. The Non-Convex Case. When P is convex, Theorem 7 guarantees an intersection-free straight-line drawing for any choice of positive weights w ij > 0. This guarantee, however, fails to hold whenever P is non-convex. While certain choices of weights could lead to an intersection-free drawing, other choices might result in intersections; in fact, a choice of weights that produces an intersection-free drawing might not even exist. See Figure 9 for an illustration. Next, we focus on the non-convex case and propose a simple geometric condition that, when satisfied, provides a similar guarantee. Boundary cones. We begin by associating a cone with the vertices of a simple polygon P. For a vertex p of P we define the cone C P at p as the intersection of the two inward-pointing open half-planes supporting the edges incident to p; see Figure 10 for an illustration. Formally, let p , p be the vertices of P adjacent to p and suppose that the triplet p , p, p traverses the boundary of the simple polygon P in counter-clockwise order. We define the two half-planes Preliminaries. where z ⊥ denotes the π/2 clockwise rotation of z. Then the cone C P at the vertex p is given by Preliminaries. . Figure 10 illustrates the cone C P for a convex vertex whose internal angle is at most π, and a reflex vertex whose internal angle is at least π. Note that this definition coincides with that of the boundary cone given in Section 2 for the continuous case; see Figure 4 for an illustration. Non-convex discrete-harmonic embeddings. Suppose y = (y 1 , ..., y n ) ∈ R 2×n is a discreteharmonic embedding into a simple non-convex polygonal domain P satisfying (7) with positive weights w = (w ij ). In this embedding, the boundary vertices v i of T are mapped to vertices of the polygon P. We shall use C P (y i ) to denote the boundary cone associated with the embedding y i ∈ R 2 of the i-th vertex v i . Preliminaries. We also note that for boundary vertices [L w (y, T )] (v i ) does not necessarily vanish and can be interpreted as the force applied on the constrained boundary vertices by their neighbors. See Figure 1 for example harmonic maps in which [L w (y, T )] (v i ) is illustrated by red arrows along the boundary. As such, it plays a role similar to the normal derivative in the continuous case; in fact, [L w (y, T )] (v i ) is proportional to the gradient of the energy corresponding to the variational form of (7) when it exists. Preliminaries. Our main result is a discrete analog of Theorem 4 and establishes a connection between the boundary cones C P and L w (y, T ) at the respective boundary vertices. We say that a boundary vertex v i satisfies the cone condition if its embedding satisfies [L w (y, T )] (v i ) ∈ C P (y i ). See Figure 11 . In turn, we show that satisfying the cone condition for the reflex boundary vertices, i.e., vertices mapped to polygon vertices whose internal angle is greater than π, is sufficient to guarantee an intersection-free embedding. Theorem 8. Let w ij > 0 be positive weights and let y = (y 1 , ..., y n ) ∈ R 2×n be a discreteharmonic embedding into a simple polygonal domain P satisfying (7) . If the cone condition [L w (y, T )] (v i ) ∈ C P (y i ) holds for all reflex boundary vertices v i of T then the straight-line drawing (y, T ) is intersection-free. Preliminaries. The proof provided in Appendix B.2 is based on reduction to the convex case: we extend the triangulation T by adding new edges (but not new vertices) into a triangulation T compatible with P , the convex hull of P; then we show how the cone condition guarantees the existence of positive weights on the edges of the extended triangulation, with which the discrete-harmonic embedding into the convex polygon P reproduces y = (y 1 , ..., y n ); finally, Tutte's Theorem 7 implies that the straight-line drawing (y, T ) of the extended triangulation T is intersection-free, and thus so is (y, T ). Preliminaries. We may further consider the piecewise-linear map φ (x,T )→(y,T ) : Ω (x,T ) → R 2 induced by such an assignment y = (y 1 , ..., y n ). As a corollary of Theorem 8, we prove in Appendix B.3 the following characterization of piecewise-linear homeomorphisms between two straight-line drawings of the same triangulation, Gortler et al. [8] also formulate sufficient conditions for invertibility in terms of reflex vertices. However, their conditions differ from the cone conditions, and the statement and proof presented there follow an index counting argument which does not readily take the form of a discrete analog of the geometric condition of Theorem 4. Preliminaries. The characterization of Theorem 9 is provided in terms of the cone condition at the reflex boundary vertices of T . Theorem 8 can be also used to derive an alternative characterization of homeomorphisms in terms of the differential of the map near the boundary. Note that φ (x,T )→(y,T ) is piecewise-linear and thus Dφ (x,T )→(y,T ) is a constant 2 × 2 matrix on the interior of every triangle. As a corollary, we can now prove the discrete analog of Theorem 3 (Alessandrini-Nesi), due to [8] : Preliminaries. Theorem 10. Let y = (y 1 , ..., y n ) ∈ R 2×n be a discrete-harmonic embedding into a simple polygonal domain P satisfying (7) with positive weights w ij > 0. Further assume that the boundary map is orientation preserving; namely, that the boundary polygons of (x, T ) and Theorem 4. Assume that γ : ∂B → Γ is an orientation preserving homeomorphism onto a simple closed curve Γ = ∂Ω that is C 1 at all but a finite set of points S ⊂ ∂B. Also assume that γ does not vanish on ∂B \ S, and that for each point in S the one-sided derivatives γ + and γ − exist, do not vanish and equal the limit of γ on the corresponding side. Preliminaries. Let φ ∈ C 2 (B, R 2 ) ∩ C 1 (B \ S, R 2 ) be a solution of (1). Further assume that everywhere on ∂B, the normal derivative ∂φ/∂ν exists, is continuous and does not vanish. The map φ is a homeomorphism of B onto Ω if and only if it satisfies the cone condition (3) everywhere on ∂B. Preliminaries. The proof of Theorem 4 provided in Section 2 is complete with the exception of Lemma 6, which argues that under the conditions of Theorem 4, for every point e iθ ∈ ∂B, the mapping φ is a local homeomorphism at e iθ . In what follows we shall prove this Lemma in a few steps: A Geometric Lemma. To simplify notations and without loss of generality we consider the following setup: We will consider the boundary point e iθ | θ=0 ∈ ∂B. We further assume it is mapped to Γ, the boundary of the target domain, in such a way that Preliminaries. for some λ > 0. In what follows we shall focus on (the more challenging) case where the derivative at e i0 is discontinuous; the same proof readily applies to smooth boundary points. With this setup, illustrated in Figure 13 , the cone condition of (3) implies that the second coordinate of the boundary map γ is monotone in a neighborhood of e i0 ; namely, we have the following Lemma: Figure 13 . The geometric setup of our proof: without loss of generality, we consider the boundary point e i0 and reorient the image such that the normal gradient ∂ ∂ν points in the negative x direction. Preliminaries. Lemma 11. Denoting γ = (γ 1 , γ 2 ), the cone condition at e i0 implies that for some δ > 0 and all s, t ∈ [−δ, δ] with s < t we have Preliminaries. where c > min γ +,2 , γ −,2 /2 > 0 depends on the opening angle of boundary and the magnitudes of the one-sided tangential derivatives. Preliminaries. Proof. Follows from plugging in (9) into (10) and local continuity. Preliminaries. Note that Lemma 11 is nothing but the local monotonicity reported previously in 5, which can be conveniently expressed in terms of the second coordinate of γ when the normal direction aligns with the x − axis (see Figure 13 ). An Analytic Lemma. Preliminaries. Lemma 12. Let f : ∂B → R with ∂B parameterized by the (periodized) segment [−π, π]. Let F : B → R be the harmonic extension defined by π] , and satisfies Preliminaries. for all s, t ∈ [−δ, δ], then there exists R < 1 such that for all r ∈ (R, 1) and all s, t ∈ [−δ/8, δ/8] with s < t, the harmonic extension F satisfies Preliminaries. Proof. Set σ = s − t. Note that 0 < σ < δ/4. We have Preliminaries. Next, we will show that each term Q j satisfies |Q j | ≤ cσ/8. For |t | > δ/3 we have |t − s| > δ/3 − δ/8 > δ/6 and in turn cos (t − s) ≤ cos (δ/6). Therefore Preliminaries. . Preliminaries. then for any r ∈ (R, 1) Preliminaries. For the Q 2 term we use |f (t)| ≤ M to get Preliminaries. dt . Preliminaries. Note that Preliminaries. Also note that on the domain of integration |t | > δ/3 and therefore both cos (s − t ) and cos (t − t ) are less than cos (δ/6). In turn, for r ∈ (R, 1) we have Preliminaries. Hence we have Preliminaries. If we take R > 1 + c 8M (1 − cos (δ/6)) 2 −1 then 1−R R < c 8M (1 − cos (δ/6)) 2 , and thus |Q 2 | ≤ cσ/8. Preliminaries. Similarly, Proof. This follows from the definition of the Poisson kernel acting as a convolution. Preliminaries. Main Lemma. We are now ready to prove Lemma 6: Preliminaries. Under the conditions of Theorem 4, the harmonic extension φ is a local homeomorphism around all boundary points e iθ , −π ≤ θ ≤ π. Preliminaries. Proof. Without loss of generality, we consider the normalized setup described above (see Figure 13 ) and show that φ is a local homeomorphism in a neighborhood of e i0 . To that end, we will establish uniform control on the normal and tangential derivatives ∂φ ∂r re it and ∂φ ∂t re it in a neighborhood of (r, t) = (0, 1). By assumption we have ∂φ ∂r re it = (λ, 0) + o (|r − 1| + |t|) . Preliminaries. Let us write the tangential derivative as Preliminaries. The previous Lemmas imply that, in a sufficiently small neighborhood, we have that Preliminaries. This shows that Preliminaries. on a sufficiently small neighborhood of (r, t) = (0, 1). This establishes a uniform bound on the angle between the normal and tangential derivatives, ∂φ ∂r and ∂φ ∂t . Lastly, continuity implies that ∂φ ∂r and ∂φ ∂t are bounded away from zero in a small enough neighborhood of e i0 . This ensures that φ is a local homeomorphism around e i0 . A.2. Proof of Theorem 2. Proof. We begin with a simple observation: the solution to the Dirichlet problem A.2. Proof of Theorem 2. Let Γ be a simple curve enclosing a non-convex bounded domain Ω and let Γ a and Γ b denote two points whose connecting line segment is not contained in the interior of Γ. We define a homeomorphism γ : ∂B → Γ as follows: we pick two antipodal points x, y ∈ ∂B and consider a homeomorphism γ that maps γ(x) = Γ a , γ(y) = Γ b and slows down in around these points in the sense illustrated in Figure 14 . A.2. Proof of Theorem 2. x y Figure 14 . Implicit construction of γ. A.2. Proof of Theorem 2. If x 1 → x 2 and x 4 → x 3 in a way that preserves the symmetry of the construction, then the harmonic extension φ, solution of (1), converges to A.2. Proof of Theorem 2. which converges to the straight line connecting Γ a and Γ b . Thus, we obtain a homeomorphism γ (or rather an entire class) for which the harmonic extension φ : B → int(Ω). A.2. Proof of Theorem 2. Appendix B. Discrete-Harmonic Mappings: Proofs B.1. An auxiliary lemma. We begin with a simple geometric observation on intersection-free straight-line drawings of triangulations that will be used in the proofs. Suppose (y, T ) is a proper intersection-free straight-line drawing of a triangulation T . We define the cone spanned by the neighbors of a vertex v i by A.2. Proof of Theorem 2. We note that in an intersection-free drawing of a triangulation, any interior or strictly reflex boundary vertex is strictly contained in the convex hull of its neighbors (a boundary vertex is a strictly reflex boundary vertex if its internal angle is strictly larger than π). Alternatively, this observation can be expressed in terms of the cones B(y, T ) as follows, .., y * n ) ∈ R 2×n is a discrete-harmonic embedding into P with positive weights w ij > 0, and assume that the cone condition [L w (y * , T )] (v i ) ∈ C P (y * i ) holds for all reflex boundary vertices. We wish to show that (y * , T ) is an intersection-free straight-line drawing, triangulating the non-convex polygonal domain P. A.2. Proof of Theorem 2. Our constructive proof is based on reduction to the convex case, where we apply Tutte's Theorem 7 to obtain an intersection-free triangulation of P = Conv(P), the convex hull of P. We break the proof into two main parts: (a) We extend the triangulation T , by adding new edges but no new vertices, into a triangulation T compatible with P , the convex hull of P. We use the Jordan-Schönflies theorem to prove that the extended triangulation is valid and satisfies the assumptions required for applying Theorem 7 on the convex polygon P . (b) We show how to construct positive weights w ij > 0 on the edges of of the extended triangulation T such that the straight-line drawing (y * , T ) satisfies (7) for all interior vertices of T . Theorem 7 then implies that (y * , T ) is an intersection-free and thus so is (y * , T ), which concludes the proof. (a) Convex extension. We first extend the triangulation via convex completion. We consider the case where P is non-convex, otherwise the assertion is readily satisfied by Theorem 7. Let P be the convex hull of P and let P ∆ denote the polygon (or collection of polygons) enclosed between P and P. P ∆ is a union of simple polygons and can therefore be triangulated by adding new edges without adding new vertices, for example, by applying the ear clipping algorithm and the Two Ears Theorem [21] . Note that the vertices of P ∆ correspond to the boundary vertices of T , and are therefore a subset of its vertices. Therefore, such a triangulation of P ∆ is, in fact, an intersection-free straight-line drawing y * , T ∆ , with T ∆ = (V, E ∆ , F ∆ ) encoding the triangles generated for triangulating P ∆ . Figure 15 illustrates the different components and notations used above. Figure 15 . Extending the triangulation T with respect to the convex hull P of P. A.2. Proof of Theorem 2. Note that, with these notations, T and T ∆ share the same set of vertices, where in the latter we allow some vertices to remain unreferenced, i.e., some of the vertices of T ∆ do not belong to any face or edge. In turn, we define the extended triangulation T = (V, E , F ) to be the union of T and T ∆ , obtained by combining their sets of faces F = F ∪ F ∆ and edges E = E ∪ E ∆ . A.2. Proof of Theorem 2. To ensure we can use Theorem 7 on the extended triangulation T we need to show that T is a 3-connected triangulation and that it has disk topology. 3-connectedness is obvious, as T and T share the same set of vertices and, thought of as a graph, the degree of each vertex of T is at least that of T . To establish that T has disk topology we need to show that it admits a proper intersection-free drawing. To this end, we show that a drawing of newly introduced triangles T ∆ can be nicely "stitched" along the boundary of the intersection-free drawing (x, T ) in an intersection-free manner (though not necessarily using straight lines), as illustrated in Figure 16 . A.2. Proof of Theorem 2. To this end, we use the Jordan-Schönflies theorem [22] : A.2. Proof of Theorem 2. Theorem 15 (Jordan-Schönflies). If h is a homeomorphism of a simple closed curve γ onto a simple closed curve γ , then h can be extended into a homeomorphism of the whole plane. A.2. Proof of Theorem 2. This theorem implies that there exists a homeomorphism of the entire plane ψ : R 2 → R 2 extending the correspondence between the boundary ∂P of the polygon P and the boundary ∂Ω (x,T ) of the drawing (x, T ). In turn, the intersection-free straight-line drawing y * , T ∆ can be mapped via the homeomorphism ψ into an intersection-free (not necessarily straight-line) drawing which we denote ψ y * , T ∆ . Note that the polygon Ω (x,T ) contains the drawing (x, T ) of T . On the other hand, the drawing y * , T ∆ of T ∆ is entirely contained in the complement of P. Consequently, the Jordan-Schönflies theorem implies that the drawing ψ y * , T ∆ of T ∆ and the drawing (x, T ) of T do not overlap, except on ∂Ω (x,T ) where it ensures they are consistent. In turn, the triangulation T , which is the union of the triangulations T and T ∆ , admits an intersection-free drawing by taking the union of the two drawings (x, T ) and ψ y * , T ∆ . See Figure 16 for an illustration. (b) Discrete-harmonic embedding of the extension. We now focus on the extended triangulation T and the straight-line drawing (y * , T ) with vertex coordinates y * ∈ R 2×n . We will show that the straight-line drawing (y * , T ) is an intersection-free triangulation of the convex polygon P . Consequently, since T ⊂ T , this will show that (y * , T ) is intersection-free as well, thus concluding the proof. A.2. Proof of Theorem 2. To show that (y * , T ) is intersection free, we construct positive weights w ij > 0 on the edges of the extended triangulation T such that the vertex coordinates y * satisfy (7) for all interior vertices of T . In turn, since y * maps the boundary of T to the boundary of a convex polygonal domain P , Theorem 7 shows that the straight-line drawing (y * , T ) is intersection-free. A.2. Proof of Theorem 2. To construct weights w = w ij on the edges of the extended triangulation T we independently consider each vertex v i ∈ V and choose weights on its incident (directed) edges in T such that Figure 16 . Using the Jordan-Schönflies theorem to "stitch" the newly introduced triangles T ∆ along the boundary of the intersection-free drawing (x, T ) in an intersection-free manner A.2. Proof of Theorem 2. There are several cases to consider, see Figure 17 for an illustration: A.2. Proof of Theorem 2. (1) v i is a boundary vertex of the extension T : Its coordinate y * i is fixed to a vertex of P regardless of the choice of weights w ij and (7) need not be satisfied. A.2. Proof of Theorem 2. (2) v i is interior to the original triangulation T : In this case we copy the original weights and set w ij = w ij > 0 for all j ∈ N T (v i ). A.2. Proof of Theorem 2. Since v i has the same neighborhood in both T and its extension T , we have [L w (y * , T )] (v i ) = 0. (3) v i is interior to T but belongs to the boundary of T : As such, v i is mapped in the drawing (y * , T ) to either a strictly convex or a reflex vertex of the polygon P: (a) If v i is mapped to a strictly convex vertex of P (whose internal angle is strictly smaller than π), it is a strictly reflex vertex of the complementary polygon P ∆ with respect to the convex hull. Applying Lemma 14 to the triangulation y * , A.2. Proof of Theorem 2. in the extended triangulation T and hence there exist positive weights w ij > 0 such that [L w (y * , T )] (v i ) = 0. (b) Lastly, consider the case where v i is mapped to a reflex vertex of P. In this case, by the assumptions made in the theorem, we know that v i satisfies the cone condition A.2. Proof of Theorem 2. Since v i is a reflex vertex of P, it is a convex vertex with respect to the triangulation y * , T ∆ of the complementary polygon P ∆ . In this case, we note that B(y * , T ∆ ) (v i ) and C P (y * i ) are opposite cones, see Figure 17 . Figure 17 . The different cases considered in the proof of Theorem 8 and key objects discussed in each case. A.2. Proof of Theorem 2. where the second equality is simply the definition of L w (y * , T ). We then choose w ij to be either w ij , w ∆ ij or their sum (for the boundary edges of T incident to v i ), which satisfy [L w (y * , T )] (v i ) = 0. With weights chosen as described above, [L w (y * , T )] (v i ) = 0 for all interior vertices v i of T . Theorem 7 then implies that the straight-line drawing (y * , T ) is intersection-free and thus so is (y * , T ), which concludes the proof. B.3. Proof of Theorem 9. Suppose φ (x,T )→(y,T ) is a piecewise-linear homeomorphism of Ω (x,T ) onto P. We want to show the existence of positive weights w ij > 0 such that y satisfies (7) and the cone condition [L w (y, T )] (v i ) ∈
{'paper_id': '209862559', 'title': 'Non-Convex Planar Harmonic Maps', 's2_url': 'https://api.semanticscholar.org/CorpusID:209862559', 'source': 'S2ORC'}