text:
Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique

We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over any specific set of $N$ points in the plane. More specifically, we bound the ratio between the number of spanning cycles (or perfect matchings) that can be embedded over a point set and the number of triangulations that can be embedded over it. The respective bounds are $O(1.8181^N)$ for cycles and $O(1.1067^N)$ for matchings. These imply a new upper bound of $O(54.543^N)$ on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of $N$ points in the plane (improving upon the previous best upper bound $O(68.664^N)$). Our analysis is based on Kasteleyn's linear algebra technique.

Introduction
Finding a Hamiltonian cycle in a graph is NP-complete even if the graph is known to be planar [7]. Counting the number of Hamiltonian cycles that are contained in a graph is #P-complete even if the graph is known to be planar and all of its vertices have degree three [15]. In this paper we consider a more general case (and thus, probably more difficult) concerning the number of all crossing-free straight-edge Hamiltonian cycles that can be embedded over a specific set of points in the plane. That is, given a set S of labeled points in the plane, we consider the number of Hamiltonian cycles that have a straight-edge planar embedding over S.
We only consider the problem of obtaining an upper bound for the number crossing-free straightedge Hamiltonian cycles that can be embedded over a set of N points in the plane. To do this, we rely on Kasteleyn's technique [14], and on edge-flipping techniques that were developed in a previous paper by the authors [9]. No familiarity with [9] is necessary, since we re-introduce all the notions that we require from it. We now give a detailed and more formal definition of the problem.
A planar graph is a graph that can be embedded in the plane in such a way that its vertices are embedded as points and its edges are embedded as Jordan arcs that connect the respective pairs of points and can meet only at a common endpoint. A crossing-free straight-edge graph is a plane embedding of a planar graph such that its edges are embedded as non-crossing straight line segments. In this paper, we only consider crossing-free straight-edge graphs. Moreover, we only consider embeddings where the points are in general position, that is, where no three points are collinear. (For upper bounds on the number of graphs, this involves no loss of generality, because the number of graphs can only grow when a degenerate point set is slightly perturbed into general position.) For simplicity, we sometimes refer to such graphs as plane graphs.
We focus on upper bounding the maximal number of plane spanning cycles (also known as Hamiltonian cycles, Hamiltonian tours, and simple polygonizations) that can be embedded over a fixed set of points in the plane. For a set S of points in the plane, we denote by C(S) the set of all crossing-free straight-edge spanning cycles of S, and put sc(S) := |C(S)|. Moreover, we let sc(N ) = max |S|=N sc(S). So, in other words, the main goal of this paper is to obtain sharp upper bounds on sc(N ).
There are many similar variants of this problem, such as bounding the number of plane forests, spanning trees, triangulations, and general plane graphs. Recent work on some of these variants can be found in [1,9,21], and we try to keep a comprehensive list of the up-to-date bounds in a dedicated webpage 1 . It seems that the case of spanning cycles is the most popular one, already considered in [2,3,4,5,6,17,24] and many others. Moreover, spanning cycles were the first case for which bounds were published, namely the bounds 3/20·10 N/3 ≤ sc(N ) ≤ 2·6 N −2 ·(⌊N/2⌋)! in [17]. A brief history of the steady progress on bounding the number of spanning cycles can be found in a dedicated webpage by Erik Demaine 2 . Currently, the best known lower bound is sc(N ) = Ω(4.642 N ), due to García, Noy, and Tejel [6], and the previous upper bound is sc(N ) = O(68.664 N ) by Dumitrescu et al. [5]. We derive the improved bound sc(N ) = O(54.543 N ).
These problems have also been studied from an algorithmic point of view, deriving algorithms for enumeration or counting of the plane graphs (or other graph types) that can be embedded over a given point set (such as in [13,19]). The combinatorial upper bounds are useful for analyzing the running times of such algorithms, and also to answer questions such as "how many bits are required to represent a triangulation (or any other kind of plane graphs)?".
Our bound (as do some of the previous bounds) relies on triangulations. A triangulation of a set S of N points in the plane is a maximal plane graph on S (that is, no additional straight edges can be inserted without crossing some of the existing edges). For a set S of points in the plane, we denote by T (S) the set of all triangulations of S, and put tr(S) := |T (S)|. Moreover, we let tr(N ) = max |S|=N tr(S). Currently, the best known bounds for tr(N ) are tr(N ) < 30 N [21], and tr(N ) = Ω(8.65 N ) [5].
The upper bound by Dumitrescu et al. [5] is obtained by proving that for every set S of N points in the plane sc(S) = O 2.2888 N · tr(S). This has sharpened an earlier bound of Buchin et al. [4], who showed that every triangulation T of S contains at most 30 N/4 ≈ 2.3404 N spanning cycles (i.e., cycles whose edges belong to T ), implying 3 that sc(S) < 2.3404 N · tr(S). Combining the above ratio with the bound tr(N ) < 30 N directly implies the asserted bound. We derive our bound in a similar manner, showing that sc(S) = O 1.8181 N · tr(S) = O(54.5430 N ).
In spite of our improved bound, we strongly believe, and conjecture, that for every point set S (of size at least N 0 , for some constant N 0 ) one has sc(S) < tr(S), and perhaps even a much sharper ratio holds. The best lower bound for this ratio that we know of is obtained from the double chain configuration, presented in [6] (and depicted in Figure 1). It is shown in [6] that when S is a double chain configuration, tr(S) = Θ * 8 N and sc(S) = Ω * 4.64 N . 4 Thus, in this case, sc(S)/tr(S) = Ω * (0.58 N ). (It is stated in [1], albeit without proof, that sc(S) = O(5.61 N ), so this example supports our conjecture.) In Section 2 we go over the preliminaries required for our analysis. These include, among others, the edge-flip techniques used in [9]. Section 3 derives the bound sc(S) = O 12 N/4 · tr(S) = O 1.8613 N · tr(S) for any set S of N points in the plane. As part of this derivation, we describe Kasteleyn's technique for counting perfect matchings and present a new way of applying it. In Section 4 we use the same methods to prove an upper bound on the ratio between the number of plane perfect matchings and the number of triangulations, showing that pm(S) = O(1.1067 N )·tr(S) (where pm(S) is the number of matchings that can be embedded over the point set S). Finally, Section 5 contains a more complex analysis of spanning cycles, implying the improved bound sc(S) = O 10.9247 N/4 · tr(S) = O 1.8181 N · tr(S).

Preliminaries
In this section we establish some notations and lemmas that are required for the following sections.
Given two plane graphs G and H over the same point set S, if every edge of G is also an edge of H, we write G ⊆ H.
Hull edges and vertices (resp., interior edges and vertices) of a graph embedded on a point set S are those that are part of the boundary of the convex hull of S (resp., not part of the convex hull boundary).
Given a set S of N points in the plane, we denote by h the number of hull vertices of S, and put n = N − h, which is the number of vertices in S interior to its convex hull.

The support of a graph
Let us denote by sc ∆ (N ) the maximal number of plane spanning cycles that can be contained in any fixed triangulation of a set of N points in the plane. Moreover, denote the set of spanning cycles contained in a triangulation T by C(T ), so sc ∆ (N ) = max |S|=N, T ∈T (S) |C(T )|.
Any spanning cycle (or, for that matter, any plane graph) is contained in at least one triangulation. Therefore, we can upper bound the number of spanning cycles of a set S of N points in the plane by going over every triangulation T ∈ T (S) and counting the number of spanning cycles contained in T . This implies the bound sc(N ) ≤ tr(N ) · sc ∆ (N ). Applying the bounds tr(N ) < 30 N from [21] and sc ∆ (N ) ≤ 30 N/4 from [4], we obtain sc(N ) < 30 5N/4 ≈ 70.21 N .
This bounding method seems rather weak since it potentially counts some spanning cycles many times. For example, consider a spanning cycle consisting of two convex chains facing each other, as depicted in the left-hand side of Figure 1. García, Noy, and Tejel [6] show that such a spanning cycle is contained in Θ * (8 N ) triangulations of its point set. Therefore, the above method will count this spanning cycle Θ * (8 N ) times. However, as stated in [1], this point set has only O(5.61 N ) spanning cycles.
In order to deal with this inefficiency, we define the notion of support (the same notion was also used in [5,9,21,22,25]). Given a plane edge graph G embedded over a set S of points in the plane, we say that G has a support of x if G is contained in (exactly) x triangulations of S; we write supp(G) = x. Notice that because every spanning cycle C contributes exactly one to the right side of the equation (it appears in supp(C) terms of the first sum, and contributes 1/supp(C) in every appearance). We will use (1) to obtain better upper bounds for sc(N ), by showing that, on average, supp(C) is large.  An edge in a triangulation is said to be flippable, if its two incident triangles form a convex quadrilateral. A flippable edge can be flipped, that is, removed from the graph of the triangulation and replaced by the other diagonal of the corresponding quadrilateral. Such an operation is depicted in Figure 2(a), where the edge ce can be flipped to the edge ad.

Ps-flippable edges
In [9], we present the concept of pseudo simultaneously flippable edges (or ps-flippable edges, for short). Given a triangulation T , we say that a subset F of its edges is a set of ps-flippable edges if the edges of F are diagonals of interior-disjoint convex polygons (whose boundaries are also parts of T ). For example, in Figure 2(b), the three dashed edges form a set of ps-flippable edges, since they are diagonals of interior-disjoint convex quadrilateral and convex pentagon (another set of ps-flippable edges, in a different triangulation, is depicted in Figure 2(c)).
Ps-flippable edges are related to convex decompositions. A convex decomposition of a point set S is a crossing-free straight-edge graph D on S such that (i) D includes all the hull edges, (ii) each bounded face of D is a convex polygon, and (iii) no point of S is isolated in D. See Figure 2(c) for an illustration. For additional information about convex decompositions, see, for example, [10]. Notice that if T is a triangulation that contains D, the edges of T \ D form a set of ps-flippable edges, since they are the diagonals of the interior-disjoint convex polygons of D (again, consider the dashed edges in Figure 2(c) for an illustration). Thus, finding a large set of ps-flippable edges in a triangulation T is equivalent to finding a convex decomposition with a small number of faces (or edges) in T .
In [9], we prove the two following lemmas.
Lemma 2.1 Every triangulation T over a set of N points in the plane contains a set F of N/2 − 2 ps-flippbale edges. Also, there are triangulations with no larger sets of ps-flippable edges.
Consider the set F ′ = F \ G of j ps-flippable edges. The convex faces of T \ F ′ can be triangulated in at least 2 j ways (the bound is tight when every edge of F ′ is a diagonal of a distinct quadrangular face of T \ F ′ ), and each of the resulting triangulations contains G. See [9] for more details. We now describe another property of convex decompositions (not discussed in [9]). Consider a set S of points in the plane and a crossing-free straight-edge graph G embedded on S. We say that an interior point p ∈ S has a valid triple of edges in G if there exist three points a, b, c ∈ S such that p is contained in the convex hull of {a, b, c} and the edges ap, bp, and cp belong to G. To simplify the notation, we refer to vertices with valid triples as valid (with respect to G), and to the other interior vertices as non-valid. Lemma 2.3 Let S be a set of points in the plane and let G be a crossing-free straight-edge graph over S that contains all the edges of the convex hull of S. Then G is a convex decomposition of S if and only if every interior vertex of S is valid with respect to G.
An interior vertex v is a reflex vertex of some face of G if and only if v is non-valid (an example is depicted in Figure 3(a)). The lemma follows by observing that G is a convex decomposition if and only if no bounded face of G has a reflex vertex.

Spanning cycles and perfect matchings
Our analysis, as most of the previous works dealing with the number spanning cycles, heavily relies on the number of plane perfect matchings on S (for example, see [4,5,24]). To see the connection between the two problems, notice that if |S| is even, every spanning cycle C is the union of two edge-disjoint perfect matchings on S; namely, the matching consisting of the even-indexed edges of C, and the matching consisting of the odd-indexed edges. An illustration of this property is depicted in Figure 3(b). Denote by M(S) the set of all plane perfect matchings on S, and put pm(S) = |M(S)|. We also set pm(N ) = max |S|=N pm(S). Hence, a simple upper bound on sc(S) is pm(S) 2 . In general, the union of two edge-disjoint perfect matchings is not always a spanning cycle, but it is a cover of S by vertex-disjoint even-sized cycles.
To deal with point sets of odd size, we use the following lemma: Proof. Consider a set S of N points in the plane, where N is odd. Pick a new point p outside the convex hull of S, and put S ′ = S ∪ {p}. Let C be a plane spanning cycle of S. Then there exists an edge e = vu of C such that p can be connected to the two endpoints u, v of e without crossing C. Indeed, this is a projective variant of the property, noted in [8], that every finite collection of non-crossing straight segments in the plane contains a segment e such that no other segment lies vertically above any point of e (see also [18,Section 8.7]). By replacing e with the edges vp and pu, we obtain a crossing-free spanning cycle of S ′ . This implies that we can map every spanning cycle of S to a distinct spanning cycle of S ′ , and thus, sc(S) ≤ sc(S ′ ). The lemma then follows since sc( Bounding the number of perfect matchings on S within a fixed triangulation T can be done by the beautiful linear-algebra technique of Kasteleyn [14], described in detail in [16,Section 8.3]; see Section 3 for more details. Buchin et al. [4] have used this technique to show that any triangulation T of S contains at most 6 N/4 perfect matchings, and at most 30 N/4 ≈ 2.3403 N spanning cycles. We also note that Sharir and Welzl [24] showed that pm(S) = O 10.05 N , completely bypassing the approach of counting matchings (or other graphs) within a triangulation.

A first bound
In this section we first review an enhanced variant of Kasteleyn's technique and then use it to derive the following initial upper bound on sc(S).

Proof.
First, by Lemma 2.4, we may assume that N is even. Consider a triangulation T of S. As already observed, every spanning cycle contained in T is the union of two edge-disjoint perfect matchings contained in T . Given a plane graph G, we denote by M(G) the set of all perfect matchings that are contained in G. Recalling (1), we have .
(The inequality comes from the fact that not every pair M 1 , M 2 of matchings, as in the sum, necessarily yields a spanning cycle.) Let us fix the "first" perfect matching M 1 ⊂ T ; as mentioned above, Buchin et al. [4] prove that |M(T )| ≤ 6 N/4 , so there are at most 6 N/4 choices of M 1 . Next, we construct a convex decomposition D such that M 1 ⊂ D ⊂ T , as follows. We start with M 1 and add all the missing hull edges; let us denote the resulting graph as D ′ . By Lemma 2.3, it suffices to ensure that every interior point p ∈ S is connected in D to (at least) three points a, b, c ∈ S, such that p is inside the convex hull of {a, b, c}. Every interior vertex p of S has degree 1 in D ′ , so we start by setting D := D ′ , and then, for each interior point p ∈ S, we add to D two additional edges of T adjacent to p, so as to create a valid triple. To do so, let e be the edge of D ′ (that is, of M 1 ) incident to p, and let λ be the ray emanating from p in the opposite direction. Let e 1 (resp., e 2 ) be the first edge of T incident to p encountered in clockwise (resp., counterclockwise) direction from λ; see Figure 4(a). Then {e, e 1 , e 2 } is a valid triple of edges, and we add e 1 , e 2 to D. After applying this step to each interior point p, the resulting graph D is indeed a convex decomposition of S. We denote by F the set of edges that are in T but not in D. The edges of F are diagonals of interior-disjoint convex polygons, and thus F is a set of ps-flippable edges. By Euler's formula, the triangulation T contains 3N − 2h − 3 interior edges, and D contains at most 2n + N/2 interior edges (at most N/2 edges of M 1 and 2n added edges to form n valid triples). Therefore, Remark. Note the strength of this bound: Lemma 2.1 has a rather involved proof, given in [9], and it yields a set of N/2 − 2 ps-flippable edges in the entire triangulation. In contrast, here we get the same number (minus 1) after we remove from T an arbitrary perfect matching, with a considerably simpler analysis. Thus the significance of the analysis in [9] (involving Lemma 2.1) is only for triangulations which contain no perfect matching on S. For example, any triangulation with more than N/2 interior vertices of degree 3 cannot contain a perfect matching, since, as is easily checked, two interior vertices of degree 3 cannot share an edge.
Without loss of generality, we assume that F consists of exactly N/2 − 3 edges. We now proceed to bound the number of ways to choose the second matching M 2 while taking the supports of the resulting graphs M 1 ∪ M 2 into account. Since M 1 and M 2 have to be edge-disjoint, we can remove the N/2 edges of M 1 from T , and remain with a subgraph T ′ that has fewer than 5N/2 edges. Next, we define a weight function µ over the edges of T ′ , such that every edge in F has a weight of 1 and every other edge has a weight of 1/2. We define the weight µ(M 2 ) of a perfect matching M 2 ⊂ T ′ as the product of the weights of its edges. Therefore, if M 2 contains exactly j edges of F , then µ(M 2 ) = (1/2) N/2−j . Moreover, for such a matching M 2 , we have |F \ M 2 | = N/2 − 3 − j.
Clearly, F \ M 2 is also a set of ps-flippable edges, none of which belongs to M 1 ∪ M 2 . We thus have 1 supp(M 1 ∪ M 2 ) ≤ 1 2 N/2−3−j = 8µ(M 2 ), which implies that, given a specific triangulation T and a specific perfect matching M 1 ⊂ T , with T ′ = T \ M 1 , as above.
Kasteleyn's technique: An enhanced version. We now apply an extension of Kasteleyn's technique to estimate the sum in the right-hand side of (2). Here is a brief overview of the technique being used (where instead of the original technique, we apply a weighted extension of it). Given an oriented graph 5 G = (V, E) with no anti-parallel edges and a weight function µ over the edges, we define the following weighted adjacency matrix An easy extension of Kasteleyn's theorem states that every planar graph G can be oriented into some digraph G such that, for any real-valued weight function µ on its edges, we have  (recall that µ(M ) = e∈M µ(e)). In the "pure" form of Kasteleyn's theorem µ ≡ 1 (i.e., G is unweighted) and the left-hand side is just the squared number of perfect matchings in G. A detailed presentation of Kasteleyn's theorem can be found in [16,Section 8.3]. The extension to weighted graphs is given in Exercise 8.3.9 therein. We denote by b i the column vectors of B, for 1 ≤ i ≤ N , and estimate the above determinant using Hadamard's inequality Applying the above machinery to our plane graph T ′ (i.e., using (3) and (4)), with the edge weights µ as defined above, we have 5 We follow here the notation used in [16] to denote a digraph obtained from an underlying undirected graph by giving each of its edges an orientation.
(where we have used the arithmetic-geometric mean inequality and the fact that every edge of T ′ has two corresponding matrix entries). We note that the bound 6 N/4 on the number of perfect matchings in a triangulation T is obtained in [4] by applying the unweighted version of Kasteleyn's theorem to the entire T . In this case e∈T µ(e) 2 is the number of edges of T , which is at most 3N , and the bound follows.
By noting that and combining this with (2) and (5), we obtain Recalling once again that a triangulation contains at most 6 N/4 perfect matchings [4] (that is, there are 6 N/4 ways of choosing M 1 ), and combining this with (6), we obtain

Perfect matchings and triangulations
In this section we apply the machinery of the previous section to derive an upper bound on the ratio between the number of plane perfect matchings and the number of triangulations. As already mentioned in Section 2, Kasteleyn's technique implies that a triangulation of a set of N points can contain at most 6 N/4 perfect matchings (see [4]). This implies that for every set S of N points in the plane, pm(S) ≤ 6 N/4 · tr(S) ≈ 1.5651 N · tr(S). We will improve this bound, using lower bounds on the supports of perfect matchings, in a manner similar to that in Section 3. Before proceeding, we note the following lower bound on the ratio pm(S)/tr(S). Let S be a double circle configuration, depicted in Figure 4(b), consisting of N points (see [11] for a precise definition). An inclusion-exclusion argument implies that tr(S) = 12 N/2 (see [11,20]). Moreover, Aichholzer et al. [1] proved that pm(S) = Θ * (2.2 N ). Therefore, in this case, pm(S)/tr(S) ≈ Θ * (0.635 N ).
We now present an improved upper bound for this ratio.
Consider a triangulation T ∈ T (S) and a perfect matching M ⊆ T . As shown in the proof of Theorem 3.1, there exists a set of N/2 − 3 ps-flippable edges in T \ M . Therefore, the support of M is at least 2 N/2−3 . Combining this with (7) implies As already mentioned above, this does not imply a new bound on pm(N ), since Sharir and Welzl [24] showed that pm(S) = O 10.05 N , bypassing the approach of counting matchings within a triangulation. We are not aware of any construction for which pm(S) ≥ tr(S), and offer the conjecture that there exists a constant c < 1 such that pm(S) = O(c |S| · tr(S)) for every finite set S of points in the plane. (See also the conjecture concerning spanning cycles, made in the introduction.)

An improved bound
In this section we present a more complex analysis for the number of spanning cycles, obtaining a slightly better bound than the one presented in Section 3. The analysis has three parts, each presented in a separate subsection. Let

A v 3 (T )-sensitive bound
In this subsection we derive the following bound, which is a function of N and v 3 (T ).
Lemma 5.1 Let T be a triangulation over a set S of N ≥ 6 points in the plane, such that N is even and S has a triangular convex hull; also, let v 3 (T ) = tN . Then Proof. As before, we treat every spanning cycle as the union of two edge-disjoint perfect matchings M 1 , M 2 ∈ M(T ). We start by bounding the number of ways to choose the first perfect matching M 1 . For this, we use the standard variant of Kasteleyn's technique, with the weight function µ ≡ 1 (i.e., G is unweighted).

Recall the inequality
obtained in Equation (5), where the b i (for 1 ≤ i ≤ N ) are the column vectors of the adjacency matrix of the oriented graph T . Substituting µ ≡ 1, the left hand side becomes the number of perfect matchings in T , and the squared norm of each column vector is the degree of the vertex corresponding to that column. Since every column that corresponds to a vertex of degree 3 has a squared norm of 3, the product of the squared norms of these is 3 v 3 (T ) = 3 tN . For the remaining N − v 3 (T ) columns, we use, as in Section 3, the arithmetic-geometric mean inequality to bound the product of their squared norms (as in Equation (5)). This yields the bound where X is the sum of the degrees of all vertices other than those counted in v 3 (T ). The sum of the degrees over the vertices of any specific triangulation is smaller than 6N , and the sum of the degrees of the interior degree-3 vertices in T is 3v 3 (T ). Therefore, we have Combining (8), (9), and the product of the squared norms that correspond to interior vertices of degree 3, implies that the number of ways to choose M 1 is less than Next, let us fix a specific perfect matching M 1 ∈ M(T ). As shown in the beginning of the proof of Theorem 3.1, there exists a set F of N/2 − 3 ps-flippable edges in T , none of which belongs to M 1 . We continue as in the proof of Theorem 3.1, by assigning a weight of 1 to the edges of F and a weight of 1/2 to the rest of the edges of T \ M 1 , and then applying Kaseteleyn's technique to bound the sum where b ′ i are the column vectors of the oriented adjacency matrix of T \ M 1 (recall (2)). An interior vertex v of degree 3 in T has only two edges adjacent to it in T \ M 1 , both not in F (since an edge adjacent to an interior vertex of degree 3 cannot be flippable). Therefore, the squared norm of a matrix column that corresponds to such a vertex is (1/2) 2 + (1/2) 2 = 1/2, and the product of the squared norms of all such columns is 1/2 v 3 (T ) = 1/2 tN .
For the remaining N − v 3 (T ) columns, we may once again use the arithmetic-geometric mean inequality to obtain a bound similar to the one in (8). However, this time we get a different value for X, since (i) some of the edges of T were removed, and (ii) some of the remaining edges were reweighted. The edges of F have remained and still have a weight of 1 each, so they contribute at most 2 · (N/2 − 3) · 1 < N to X. Every other edge contributes 2 · 1/4 = 1/2 if it is not incident to an interior vertex of degree 3 in T , and 1/4 otherwise. Since a triangulation has fewer than 3N − 3 edges, there are fewer than 2N edges in T \ {F ∪ M 1 }, and we get By combining this with the rest of the squared norms and with the present version of (8), we have Finally, to complete the proof, we combine (10) and (11), and obtain

Remark.
Notice that in the worst case (i.e., when t = 0) we obtain the same asymptotic value as in our initial bound of 12 N/4 . Similarly, the bound in (10) becomes 6 N/4 when t = 0, as in Buchin et al. [4].

A flip(T )-sensitive bound
Hurtado, Noy, and Urrutia [12] prove that that flip(T ) ≥ N/2 − 2, and that this bound is tight in the worst case (the upper bound is also implied by Lemma 2.1; see also [9]). In this subsection we obtain a bound as a function of flip(T ), which improves our initial bound of 12 N/4 when flip(T ) is larger than N/2 by some positive fraction of N . We start by mentioning two basic properties of triangulated polygons. Ears. Given a triangulated polygon P , an ear of P is a bounded face of the triangulation with two of its edges on the boundary of P . It can easily be shown that every triangulated simple polygon with at least four edges contains at least two ears (whose boundary edges are all distinct). For example, the two ears of the triangulated polygon in Figure 5(a) are shown shaded.

Catalan numbers. The N -th Catalan number is
. It is well known that a convex polygon with N vertices has C N −2 triangulations (e.g., see [23,Section 5.3]). Therefore, the number of triangulations of a convex polygon with d ≥ 1 diagonals is (the inequality can easily be verified by induction).
Next, we define c gon as the maximum real number satisfying the following property. Every simple polygon P that has a triangulation T P with k of its diagonals flippable and with l ≤ k of these diagonals forming a ps-flippable set, has at least 2 l c k−l gon triangulations. Notice that the triangulations under consideration, including T P , are triangulations of the polygon P , and not of its vertex set.
17965 the unique real root of the polynomial 1 + 4x 2 − 4x 3 . That is, every simple polygon P that has a triangulation T P with k of its diagonals flippable and with l ≤ k of these diagonals forming a ps-flippable set, has at least 2 l x k−l triangulations.
Proof. Figure 5(b) depicts a polygon that implies the upper bound.
We prove the lower bound by induction on l and k. To have some base case for this induction, notice that when l = k, P has at least 2 k = 2 l x k−l triangulations.
Next, consider a polygon P and a triangulation T P of P , such that T P contains a maximal set F of l ps-flippable edges, and k − l > 0 flippable edges not in F . Let f 1 , f 2 , · · · , f j be the non-triangular faces of the convex subdivision T P \ F . (Notice that T P \ F is a convex subdivision of a polygon, and not of the convex hull of a point set.) Each f i is a convex polygon with m i ≥ 4 sides and m i − 3 diagonals, and thus, l = j i=1 (m i − 3). A flippable edge not in F must be on the boundary of some f i , since otherwise F is not maximal. We say that such a flippable edge e / ∈ F is covered by a face f i if (i) e is on the boundary of f i , and (ii) the triangle ∆ in T P that is contained in f i and incident to e has two edges in F (so e is the only edge of ∆ on the boundary of f i ). Ears are incident to two edges of their containing f i , and thus, cannot cover any edge. Since any triangulated polygon contains at least two ears, with four distinct boundary edges, a polygon with m sides (and m − 3 diagonals) can cover at most m − 4 edges. Therefore, if all flippable edges not in F are covered, then k − l ≤ j i=1 (m i − 4). By multiplying the number of triangulations of the f i 's and applying (12), we get that the number of triangulations of P that contain T P \ F is at least We are left with the case where there is a flippable edge e / ∈ F that is not covered by any f i . Let e ′ be the edge obtained by flipping e. We now derive a lower bound on the number of triangulations of P that contain e and on the number of triangulations of P that contain e ′ . To bound the number of triangulations that contain e, we partition P into two interior disjoint simple polygons P ′ , P ′′ by "cutting" P at e. More precisely, we consider the two triangulated polygons T P ′ , T P ′′ ⊂ T P . Together, these two triangulated polygons contain k − 1 diagonals that are flippable. Moreover, the set F remains a set of l ps-flippable edges which are diagonals of the two polygons. Thus, the induction hypothesis implies that there are at least 2 l x k−1−l triangulations of P that contain e.
To obtain a similar bound for the number of triangulations containing e ′ , we produce at most four triangulated sub-polygons of T P by removing the two triangles incident to e (which cover the same quadrilateral covered by the two triangles incident to e ′ in the new triangulation). Such a case is illustrated in Figure 6(a), where the triangles incident to e ′ are shaded. This partitioning may cancel the flippability of at most five edges (those incident to the two triangles adjacent to e). At most two out of the five edges may be ps-flippable, since e can only be incident to ears of polygons of T P \ F . Using the induction hypothesis again, we get that there are at least 2 l−2 x (k−5)−(l−2) = 2 l−2 x k−l−3 triangulations that contain e ′ (and the four edges around it). Therefore, P has at least Notice that any spanning cycle partitions the convex hull of its point set into interior-disjoint simple polygons; an example of such a partition is illustrated in Figure 5(b). The support of the spanning cycle is the product of the number of triangulations of each of these polygons. For a fixed choice of M 2 (and of M 1 ), denote by P 1 , . . . , P m the polygons in the partition produced by M 1 ∪ M 2 . For each i, let k i be the number of flippable diagonals of P i , and let l i be the number of those diagonals (among the k i flippable ones) that belong to F . If Applying Lemma 5.2 to each P i and multiplying the resulting bounds, we obtain a total of at least 2 l i x k i − l i triangulations. Hence, Next, notice that µ(M 2 ) = 2 l x flip T (M 2 )−l , so we have By combining (13) with Kasteleyn's method, we obtain To bound the sum in the parentheses, we write flip T (M 1 ) = w + z, where w = |F ∩ M 1 | and z is the number of flippable edges in M 1 \ F . Then T \ M 1 contains fewer than N/2 − w edges of F , κN − z flippable edges not in F , and fewer than 2N − (κN − flip T (M 1 )) non-flippable edges. Therefore, Since x < 2, the right-hand side is maximized when w = 0 and z = flip T (M 1 ), and it then becomes Combining (14) and (15), we get To bound the sum in (16), we once again use Kasteleyn's technique. This time, we define a weight function ν(·) over the edges of T , such that every flippable edge gets a weight of γ, and every other edge a weight of 1. Notice that, in this manner, ν(M 1 ) = γ flip T (M 1 ) for every M 1 ∈ M(T ). We thus have Finally, combining (16) and (17) implies the assertion of the lemma.
Note that in the worst case, when κ = 0, the bound becomes O (10 + 2γ 2 ) N/4 . For k = 0, we have γ = x · e −(x 2 −1)/16 , and it is easy to verify that γ > 1 for 1 < x ≤ 5/4. So the bound is actually asymptotically worse than our initial bound of 12 N/4 , and it continues to be worse when κ is sufficiently small. As the next subsection shows, in this case the v 3 -dependent bound from Subsection 5.1 becomes small and can be used instead.

Integration
In this subsection we combine the results from the two previous subsections to obtain an improved bound for sc(N ). This is done by deriving a connection between v 3 (T ) and flip(T ). We start by presenting a generalization of Lemma 2.4.

Proof .
Consider a point set S. If S has an even number of points, we pick a new point p outside the convex hull of S, and denote S ′ = S ∪ {p}. As mentioned in the proof of Lemma 2.4, inserting an additional vertex outside the convex hull of the point set can only increase the number of spanning cycles. If S has an odd number of points, we denote S ′ = S. Notice that, either way, S ′ has an odd number of points. Let ∆abc be a large triangle containing S ′ in its interior, and let S ′′ = S ′ ∪ {a, b, c}. Again, since inserting an additional vertex outside the convex hull of the point set can only increase the number of spanning cycles, we have sc(S ′ ) ≤ sc(S ′ ∪ {a}) ≤ sc(S ′ ∪ {a, b}) ≤ sc(S ′′ ). Since S ′′ has an even number of points and a triangular convex hull, sc(S) ≤ sc(S ′ ) ≤ sc(S ′′ ) = O(c N +3 ) = O(c |S| ). We also require the notion of separable edges, as presented in [22]. Consider a point set S, a triangulation T ∈ T (S), and an interior point p ∈ S. We call an edge e incident to p in T a separable edge at p if it can be separated from the other edges incident to p by a line through p. An equivalent condition is that the two angles between e and its clockwise and counterclockwise neighboring edges (around p) sum up to more than π. We observe the easy following properties (see Figure 7 for an illustration).
(S0) No edge is separable at both vertices induced by its endpoints.
(S1) If p has degree 3 in T , every edge incident to it is separable (recall that p is an interior point).
(S2) If p has degree at least 4 in T , at most two incident edges can be separable at w.
(S3) If p has degree at least 4 in T and there are two edges separable at p, then they must be consecutive in the order around it.
We are now ready for our main theorem. Proof. By Lemma 5.4, we may assume that N is even and that S has a triangular convex hull. Recall that sc(S) = T ∈T (S) C∈C(T )
We sort the triangulations in the first sum according to the number of interior vertices of degree 3 that they contain, and get .
1 supp(C) . However, when v 3 (T ) is small, the improvement in Lemma 5.1 is not significant. In this case we will use instead the bound in Lemma 5.3 which, as we now proceed to show, becomes significant when v 3 (T ) is small.
Consider a triangulation T ∈ T (S). Since S has a triangular convex hull, T contains 3N − 9 interior edges. Notice that an interior edge e is flippable if and only if e is not separable at either of its endpoints (this property is equivalent to e being a diagonal of a convex quadrilateral). From the above properties of separable edges, we have


extfieldsofstudy: Medicine Physics

s2fieldsofstudy:
Computer Science
Psychology

text:
Time-Dependent Statistical and Correlation Properties of Neural Signals during Handwriting

To elucidate the cortical control of handwriting, we examined time-dependent statistical and correlational properties of simultaneously recorded 64-channel electroencephalograms (EEGs) and electromyograms (EMGs) of intrinsic hand muscles. We introduced a statistical method, which offered advantages compared to conventional coherence methods. In contrast to coherence methods, which operate in the frequency domain, our method enabled us to study the functional association between different neural regions in the time domain. In our experiments, subjects performed about 400 stereotypical trials during which they wrote a single character. These trials provided time-dependent EMG and EEG data capturing different handwriting epochs. The set of trials was treated as a statistical ensemble, and time-dependent correlation functions between neural signals were computed by averaging over that ensemble. We found that trial-to-trial variability of both the EMGs and EEGs was well described by a log-normal distribution with time-dependent parameters, which was clearly distinguished from the normal (Gaussian) distribution. We found strong and long-lasting EMG/EMG correlations, whereas EEG/EEG correlations, which were also quite strong, were short-lived with a characteristic correlation durations on the order of 100 ms or less. Our computations of correlation functions were restricted to the spectral range (13–30 Hz) of EEG signals where we found the strongest effects related to handwriting. Although, all subjects involved in our experiments were right-hand writers, we observed a clear symmetry between left and right motor areas: inter-channel correlations were strong if both channels were located over the left or right hemispheres, and 2–3 times weaker if the EEG channels were located over different hemispheres. Although we observed synchronized changes in the mean energies of EEG and EMG signals, we found that EEG/EMG correlations were much weaker than EEG/EEG and EMG/EMG correlations. The absence of strong correlations between EMG and EEG signals indicates that (i) a large fraction of the EEG signal includes electrical activity unrelated to low-level motor variability; (ii) neural processing of cortically-derived signals by spinal circuitry may reduce the correlation between EEG and EMG signals.

Introduction
Since the first publication by D. Walter [1], the coherence method, developed for the analysis of stationary random data in linear systems (see, e.g., [2]), has been employed in hundreds of papers dealing with the analysis of neural signals such as EEGs and EMGs. In these publications, the level of coherence was used as a measure of coupling between the processes generating neural signals and of the functional association between neuronal structures [3][4][5][6].
This analysis of relationships between neural signals is based on computations of the coherence and phase of the two signals. For Fourier harmonics, X (v) and Y (v), of two time-dependent signals X (t) and Y (t), the coherence is defined as the square of the modulus, C(v)~DP(v)D 2 , and the phase is defined as W(v)~arctan½Im P(v)=Re P(v), of the complex coherence function Here, Re P and Im P stand for the real and imaginary parts of the function P. Signals X (t) and Y (t) can also be sliced into M disjoint segments, fX j (t)g,fY j (t)g,j~1, . . . ,M, and the function P(v) may be estimated as shown by Eq. (1) with auto-and cross-spectral density functions computed for each segment and averaged over M segments, Coherence is considered to be statistically significant if its magnitude exceeds some value L. At any desired confidence level a% (in the most cases a~95%), the confidence limit is estimated [7] under a Gaussian assumption as: A relatively small number of segments, M, suffices to achieve any desired confidence limit due to the exponential dependence of the confidence limit on the number of segments. Neural signals are obviously nonstationary. To address the nonstationarity of biological signals, the coherence method has been generalized [8] for wavelet harmonics [9]. Wavelet-based methods allow a combined frequency-and time-domain representation of nonstationary signals.
In this paper, we propose and discuss an alternative approach to search for dynamical relationships between neural signals [10]. In this method, which is broadly employed in statistics and, in particular, in statistical physics, a relationship between two random time-dependent signals x(t) and y(t) is determined by the correlation function C(t 1 ,t 2 )* ð dxdy½x(t 1 ){m x (t 1 )½y(t 2 ){m y (t 2 )p(x,y): ð4Þ Here p(x,y) is the joint probability density function of two random variables, m x and m y are the corresponding mean values m x (t)~Ð x(t)p(x)dx and m y (t)~Ð x(t)p(y)dy, where p is the probability density function. It should be emphasized that for nonstationary systems, the time dependence of correlation functions is determined not only by the time dependencies of the signals themselves, but also by the time dependencies of the probability density functions. For two independent random variables, the joint probability density function can be factorized, i.e., p(x,y)*p(x) : p(y), and the correlation function C vanishes.
The probability density functions of neural signals are not known a priori. Therefore, one needs to have a sufficiently large set (statistical ensemble) of neural signals fx j (t)g and fy j (t)g, (j~1, . . . ,N) recorded during N epochs -in our case, trials during which a subject repeatedly performs an identical task -in order to apply the statistical method. In this approach, the integration of probability density functions in Eq. (4) is replaced by the ensemble average over many trials, where m x (t)~1 N P j x j (t) and m y (t)~1 N P j y j (t) are the mean values.
This expression becomes exact only in the limit when the number of trials goes to infinity, N??. In our experiments the number of trials was about 400, and we used Fisher's theorem [11] to compute the confidence interval for the correlation functions.
Here we applied this statistical method to an analysis of EEG and EMG signals recorded during handwriting. Handwriting [12] provides an excellent neuromuscular task for quantitative studies of statistical and correlational properties of biological signals in the time domain. Handwriting consists of relatively simple, stereotyped hand movements that involve two basic motor components: firmly holding a pen by the fingers and moving the hand and the fingers to produce written text. We recorded the mechanical events of handwriting using a digitizing tablet that electronically recorded each epoch when the pen touched the paper (pen-onpaper period), and we simultaneously recorded the cortical EEG and EMG of intrinsic muscles of the hand.
Our dataset allowed us (i) to align the mechanical events, EEG signals and EMG signals associated with handwriting and (ii) to divide all of these signals into trial segments that correspond to a sequential set of epochs as each subject performed an identical handwriting task. Our trials started 1000 ms before the first moment when the pen touched the paper and ended 1000 ms after this time. This precise temporal sequence enabled us to compare statistical and correlation properties of neural signals recorded before, during and after the actual pen-on-paper activity.
The recorded data consisted of N trials, each trial captured the activity associated with a single handwritten letter. Each trial contained EEGs recorded in n eeg channels, and EMGs recorded in n emg channels, i.e. in total, we obtained N|n eeg |n emg data files each of 2000 ms duration.
In contrast to the coherence methods used to study the relationship between neural signals in the frequency domain, our statistical method enabled us to study the statistical and correlational properties of neural signals directly in the time domain. That allows us to elucidate both dynamical patterns of activity in different cortical areas and the functional relationships between different cortical areas.
As in the case of EMG signals recorded from muscle groups involved in handwriting [13], we found that trial-to-trial variability of the ''energy'' of the EEGs recorded from the motor cortex area had a log-normal distribution, which was clearly distinguishable from the normal (Gaussian) distribution. The log-normal distribution fitted the experimental data in all time intervals during a trial, but its parameters -the mean value and dispersiondepended on time. These two variables suffice to completely describe both qualitatively and quantitatively the trial-to-trial variability of neural signals during handwriting.
We also studied time-dependent EMG/EMG and EEG/EEG correlations. We found strong and long-time EMG/EMG correlations. Correlations between EEG signals over the motor cortex area were also quite strong, but the correlations existed over relatively short durations with characteristic correlation times on the order of 100 ms or less. All subjects involved in our experiments were right-handed and wrote with their dominant hand. However, we observed equally strong inter-channel correlations when both channels were located on either the left or right hemispheres, while inter-hemispheric correlations were 2-3 times weaker.
Although we observed task-related changes in the mean energies of both EEG and EMG signals, we found that EEG/ EMG correlations were much weaker than EEG/EEG and EMG/EMG correlations. In other words, trial-to-trial variations of the magnitudes of the EEG and EMG changes were related only weakly.

Methods
This study was approved by the Institutional Review Board of Human Participants Research of Dartmouth College, Hanover, NH. No personal information was recorded during the sessions, and all data were analyzed anonymously. Written informed consent was obtained from the subjects prior to the recording sessions.
A schematic of the experimental setup for simultaneous recording EMG and EEG signals during handwriting is shown in Figure 1. We used LogiPen to record handwriting characters. EMG signals were sampled using bipolar surface EMG electrodes (Kendall Arbo). We used EMG analog amplifiers with gain 1000, low pass filter of 450 Hz, and high pass filter of 12 Hz. The EMG signals were digitized at a sample rate of 1000 Hz. The surface EMGs of the intrinsic hand muscles were recorded by two electrode pairs. One pair recorded EMG activity from flexor pollicis brevis and abductor pollicis brevis. The second pair recorded from the first dorsal interosseus muscle ( Figure 2). EEG activity was sampled with a standard 64-channel device. The data from the 64-channel EEG recording system were high-pass filtered with 8 Hz cutoff, digitized at 1000 Hz and saved on a computer. Handwriting and EMG inputs were synchronized by a LabView data acquisition program based on the pen-down event associated with each handwriting trial. We used LogiManage as the digitizer of handwriting traces. It recorded X and Y coordinates, as well as the pen-on-paper signal. EMG signals were recorded on a dedicated computer that was also connected to the EEG recording system via a parallel port. The pen-on-paper signals were used to align EEG and EMG recordings.
To carry out quantitative studies of time-dependent statistical and correlation properties of neural signals, we instructed seven subjects to write the digit ''3''. This task produced consistent motor patterns with some trial-to-trial variability. The single character was written about 400 times in 10 blocks of 40 trials. The blocks were separated by 5 minute rest intervals.
Handwriting trials were defined as the epochs starting 1000 ms before the time moment when the pen touches the tablet at the onset of writing a particular character and ending 1000 ms later. In all cases, the character was completely written before the end of the trial. After filtering the signals, their amplitudes, A emg and A eeg , containing frequencies from 8 to 450 Hz, were squared to get the signal ''intensities'' I emg~A 2 emg and I eeg~A 2 eeg . To study time-dependent statistical and correlation properties of the signals, 2000-ms trials were subdivided into 20 time intervals, each with a duration of 100 ms, and the signal ''energy'' was calculated for each of 20 intervals as the sum, where n~1720, a~172 for EMG signals and a~1764 for EEG signals, and j~17N (where N is the total number of trials), enumerate the time intervals, recording channels, and trials, respectively. The minimal length of the time intervals was dictated by the accuracy with which trials could be aligned with respect to each other. In our experiments, the accuracy of alignment did not exceeded a few tens of millisecond, which was determined by the accuracy of the digitizing tablet used to detect the first moment of time when the pen touches the paper. Therefore, we chose a 100ms time interval. This interval substantially exceeds the temporal resolution of the digitizing tablet and ensures an accurate trial alignment.
To obtain dimensionless variables for each interval and trial, the energies E emg (n,a,j) and E eeg (n,a,j) were normalized by dividing by their mean values E emg (n,a)~SE emg (n,a,j)T and E eeg (n,a)~SE eeg (n,a,j)T. Where the symbol S . . . T stands for averaging over trials, Thus, the EMG and EEG signals for each recording channel a and each trial j were characterized by dimensionless energies E eeg (n,a,j)~E emg (n,a,j)  and their time dependence was described by the discrete variable n (time interval number).

Statistics of EMG signals
We previously studied the statistical properties of EMG signals during handwriting [13]. The results of this previous study are summarized in this Section for the convenience of readers and for further comparison with the properties of the EEG signals. Correlations properties of EMG signals, which have not studied earlier, are discussed in the next Section.
1.1. Mean values and variation coefficients. Trial-averaged intensities of raw EMG signals, or EMG templates, I (temp) emg~S I emg T described the characteristic pattern of EMG activity for the handwritten character for each of two muscle groups (Figure 3a). The time dependency of the mean energies E E emg (n,a) is shown in Figure 3b. The first 9 time intervals represent the epoch preceding the first pen touch. This subject wrote the digit ''3'' with a mean duration of the pen-on-paper period (i.e., time during which the pen touched the paper) of about 600-700 ms, which corresponds to time intervals 10 through 15 or 16, while the intervals 17 through 20 correspond to the time period following the pen liftoff from the paper.
The variation coefficients, V emg (n,a), which characterize the dispersion of the data distribution, were computed as the ratio of the standard deviation to the mean energy, The variation coefficients were large for all time intervals and for both EMG channels ( Figure 3c) and ranged from about 0.3 to 1. Thus, there was a substantial dispersion of EMG signals from trial to trial, and the EMG activity during handwriting could not be adequately described in terms of mean values only. More detailed analysis of the statistical properties of the EMG signals was required.
It should be noted that while the mean energies increased during the pen-on-paper period, the dispersion decreased. EMG patterns were more consistent when the subject wrote characters than when he/she lifted the pen off the paper. This pattern of the mean-energy and dispersion was observed for all subject, characters, and muscles.
1.2. Distribution functions. We recorded a sufficiently large number of trials to approximate the theoretical probability distribution from our data. In Figure 4, the probability plots for experimental data (with no trial selection) are shown together with probability plots for the theoretical normal and log-normal distributions. It is clear that the experimental data are fitted well with the log-normal probability density function where log stands for natural logarithm. Moreover, it is clear from Figure 4 that the fitted curves for log-normal and normal distributions are easily distinguished, and that the log-normal distribution fits the data much better than the normal one.

Correlation functions of EMG signals
We observed that activation patterns of different muscles were coordinated during handwriting and the EMG bursts occurred at consistent interburst intervals. Mathematically, this relationship can be described by statistical correlation functions as described in the Introduction.
Since the logarithms of the random dimensionless energies (8a), e(n,a,j)~log½E emg (n,a,j), are normally distributed across trials for each time interval, we may assume that the joint probability density function P½e(n,a,j),e(m,b,j) for pairs of the logarithms of dimensionless energies is the joint (second order) normal probability density function [2].
where e e(n,a)~Se(n,a,j)T, and, using the Fisher transform [11], to estimate the confidence intervals for the correlations. The Pearson correlations functions, defined in Eq. (12), are normalized to the standard deviations; therefore, their moduli do not exceed 1. We have described those correlation coefficients that approached 1 and were statistically significant as ''strong'' and those that approached 0 as ''weak'' correlations. Figure  5 shows the cross-correlation function C(n,m,a~1,b~2) for two groups of muscles (EMG channels 1 and 2) involved in handwriting as a function of two times (Figure 5a) and the diagonal elements of this function at coincident time intervals n~m (Figure 5b). It is easy to see strong and long-time correlations between activities of muscle groups (Figure 5a) and particularly strong correlations at coincident time intervals. Correlations were higher outside the pen-on-paper period, when the subjects held the pen in the air, and decreased shortly before and during the pen-on-paper period.
Here again, strong correlations are clear over long time for each muscle group.

Statistical properties of EEG signals
As can be seen from the EMG templates, which indicate distinct bursts of activity (Figure 3a), and from the time-dependency of the EMG energy (Figure 3b), muscle activity was clearly patterned during the handwriting of the character. EEG activity even in the motor cortex area should not be expected to be limited to the handwriting itself and can contain other components that are not necessarily related to handwriting. Therefore, the total amplitude of EEG signal reads as is unrelated to handwriting trials, averaging over many trials should reduce its contribution to the mean values and correlation functions. Nevertheless, since we square the total amplitudes of EEG signals, the contribution of the non-handwriting activity does not vanish completely.  To indicate each EEG channel, we used conventional electrode names shown in Figure 7.
3.1. Mean values and variation coefficients. In contrast to EMG signals, we did not find prominent bursts in the EEG templates I (temp) eeg~S I eeg T for any of 64-channels that could be attributed to handwriting activity. Figure 8a represents the time behavior of the mean energy of EEG signal, E E(n,a), of channel C1, which was located over the left hemisphere.
The mean energy and variation of the EEG signal decreased about 300-400 ms before the pen-on-paper period and remained low during the actual period of writing. A similar time dependency of the mean energy was observed for channels FC5, FC3, FC1, C5, C3, CP5, CP3, and CP1 over the left hemisphere. It should be noted that during the 300-ms time period preceding the pen-onpaper period, EMG activity was increased (see Figure 3a and Figure 3b).
Thus, we found good correspondence between changes in EMG activity and EEG activity (Figure 8a) over the motor cortex. Even   though all subjects involved in our studies were right handed, similar EEG changes were observed for the midline channels Cz and CPz, and the channels FC2, FC4, FC6, C2, C4, C6, CP2, CP4, and CP6 corresponding to the right hemisphere, locations that were mirror images of the channels with synchronized EMG/ EEG activity over the left hemisphere.
As in the case of EMG signals, we defined the variation coefficient as a ratio of the standard deviation, to the mean energy, As in the case of EMG signals, the variation coefficients decreased shortly before and during the pen-on-paper period. Since the variation coefficients were quite large (Figure 8b), EEGs during handwriting could not be adequately described in terms of mean values only, and more detailed studies of their statistical properties were required. The relative magnitude of the EEG energy decrease during the pen-on-paper period was variable from subject to subject. It was maximal in the a (8-13 Hz) and, especially, b (13-30 Hz) spectral ranges and less apparent in the c (30-100 Hz) spectral range ( Figure 9).
It should be emphasized that the variation coefficients in the b spectral range, where we observed the largest relative decrease in the mean EEG energies, increased quite significantly (up to two times) in comparison to other spectral ranges.
3.2. Distribution functions. Figure 10 shows that, as in the case of EMG signals, the theoretical log-normal function fits our EEG data better than a normal distribution. The theoretical lognormal cumulative distribution function lies inside the confidence bounds computed with the confidence level of 95%. Similar results were found in all time intervals for the EEG channels corresponding to the motor cortex in both left and right hemispheres. Some small deviations observed in some of the time intervals could be attributed to a contribution of the component of EEG activity not associated with handwriting activity, A (other) eeg . Thus, the log-normal distribution effectively approximated the trial-to-trial variability of both EMG and EEG energy.
Since the relative magnitude of the EEG energy decrease during the pen-on-paper period was maximal in the b spectral range, we restricted our computations of correlation functions for EEG signals to this spectral range.

Correlation functions of EEG signals
Since logarithms of dimensionless energies of EEG signals, including energies of EEG signals in the b spectral range, where E E(n,a)~SE(n,a,j)T. First, we examined the correlation function at coincident time intervals, i.e. the diagonal elements D (n,a,b)~D(n~m,a,b). To study the spatial distribution of the EEG/EEG correlations for the motor cortex area, it was convenient to average the function D over the time intervals, and to study the averaged correlation coefficients D D(a,b) between EEG channels. This was possible because the EEG correlation functions did not vary greatly over time.
While decreases in the energy of EEG signals before and during the pen-on-paper period were observed (Figure 9a) over the motor cortex for channels from both the left (FC5, FC3, FC1, C5, C3, C1, CP5, CP3, and CP1) and right (FC2, FC4, FC6, C2, C4, C6, CP2, CP4, CP6) hemispheres, we found quite a different behavior for the correlation coefficients. Correlations were strong between channels located within the left and right parts of cortex and much weaker for channels located in opposite hemispheres. Moreover, correlations between the central channels (Cz and CPz) and channels on the left and right sides were also weak, despite the similar decreases in the EEG energy in these channels before and during the pen-on-paper period.
The left-right symmetry of the cortex activity during handwriting is seen most clearly from the ''color-coded maps'' (Figure 11), where the magnitudes of correlation coefficients are shown by color.
The statistical method enabled us to easily derive the correlation coefficients for each time interval to get a dynamical picture of functional connectivity between different neural regions of the cortex during handwriting (see Figure 12 and Figure 13). Figure 11, Figure 12 and Figure 13, the correlation magnitudes were not determined only by the spacing between channels. However, the origin of surface EEG signals is not truly localized and discrete. There can be a problem of ''volume conduction'' in which any given EEG signal recorded by an electrode may contain components created by neural activity in areas located under other (neighboring) electrodes. To address this issue, we analyzed the time-dependent correlation functions at coincident time intervals for three pairs of channels: C5/C1 (both located on the left hemisphere), C1/C2 (located on different hemispheres), and C2/C6 (both located on the right hemisphere). This analysis is presented in Figure 14. Although the interelectrode distances in all three pairs were approximately equal to each other, we observed that inter-hemispheric correlations were at least 2-5 times lower than intra-hemispheric ones for time   intervals before and during handwriting. Thus, volume conduction appears to have a small impact on the correlations that we computed based on the ensembles of identical trials.

As seen in
Moreover, in Figure 15 we present the correlation function between EEG signals recorded in channels FC5 and CP6. We observed time-dependent and statistically significant correlations on the order of 0.2-0.3 despite the maximally large (see Figure 7) spatial separation between electrodes located in the motor cortex area with the inter-electrode spacing, L, about of ffiffiffiffiffiffiffi ffi 160 p cm. The contribution of the dipole electric field generated by the cortex located under the electrode FC5 to the electrical potential recorded by the electrode CP6 was estimated in the simplest way as (h=L) 2 *1=160, where h (*1 cm) is the distance between the electrode and cortex. Thus, the contribution of the electrical field generated at FC5 to activity at CP6 was very small, and the correlation between these EEG signals cannot be attributed to the volume conduction effect.
Finally, we studied the correlation function D(n,m,a,b) dependent on two times, or two sets of time intervals (Figure 16). In sharp contrast to the case of muscle activity (Figure 7 and Figure 8), we did not find any long-time correlations between EEG signals recorded over the motor cortex. The characteristic correlation time for a single channel was of the order of 100 ms or less, as seen from Figure 16a, where the correlation function D C3 (n,m)~D(n,m) for channel C3 is plotted.   Moreover, we did not find long-time correlations between channels lying within the left, right, or central motor cortex sites. The characteristic correlation time in this case, which corresponded to the characteristic time of cross-talk between channels, was also on the order of 100 ms or less. More accurate computations of the characteristic correlation times would require a more precise trial alignment, which in our experiments was within several tens of milliseconds.
Finally, we found that correlations between channels that overlie different parts of motor cortex, e.g., channel C3 (the left part) and channel C4 (the right part) (Figure 16b), were strongest at coincident time intervals and quickly became insignificant as the time interval between recorded events increased. Thus, there were no significant long-time correlations between channels among different parts of the motor cortex.

Correlation functions of EMG and EEG signals
Since the logarithms of both EMG energy and EEG energy in motor cortex channels were normally distributed over trials, we computed the correlation functions between EMG and EEG signals as which detects simultaneous trial-to-trial variations of EEG activity and EMG activity ( Figure 17). As in the case of EEG/EEG correlation functions, we restricted our computations to the b spectral range of EEG signals. The energy of EMG signals grew in the time period shortly before and during the pen-on-paper period (Figure 3a and 3b), while the energy of EEG signals in the motor cortex channels decreased during the same time period (Figure 9b). Therefore, we expected to find an anticorrelation between EMG and EEG signals, i.e. the correlation function K would be negative in the time intervals shortly before and during the pen-on-paper period.
Although correlation coefficients at coincident time intervals, shown in Figure 18, were statistically significant at some time intervals, they were smaller than EEG/EEG and EMG/EMG correlation coefficients. When statistically significant EMG/EEG correlations occurred, they were inconsistent among subjects.
The absence of strong correlations between EMG and EEG signals may indicate that strong trial-to-trial variability may be in part introduced by spinal motoneuron activity, which results in wide dispersion of EMG signals with respect to EEG signals. Additionally, EEG components unrelated to motor output may decrease correlations between EEG and EMG signals.

Discussion
To derive a dynamical picture of neural activity and of functional relationships between different neural regions, we examined time-dependent statistical and correlation properties of EMG and EEG signals recorded simultaneously during handwriting of digit ''3'' by 7 subjects. We recorded signals in approximately 400 2000-ms trials during which each subject performed an identical handwriting task. The trials started 1000 ms before the moment of time when the pen touched paper the first time and finished 1000 ms after this moment of time. To study the time dependence of neural signals, the trials were divided into 20 100-ms time intervals.
We studied trial-to-trial variability of EMG signals and EEG signals derived from the motor cortex during the 2000-ms time interval during which subjects performed the same handwriting task. We found that the trial-to-trial distribution of the neural signal energy was described well by a log-normal distribution and not by a normal distribution. Whereas the distribution parameters -the mean value and the dispersion -depended on intra-trial time, the log-normal distribution was found for all of 20 time intervals.
We computed the Pearson auto-and cross-correlation functions for EMG signals and EEG signals recorded from the motor cortex. We observed very strong correlations at coincident time intervals between EMG signals recorded from different muscle groups. Moreover, these correlations were long-time and remained quite strong during almost the entire 2000-ms time period.
We also found strong correlations between EEG signals in b spectral range, provided that channel pairs were located in the motor cortex of the same hemisphere. The correlations between signals recorded from different sides of the skull were much weaker. Moreover, in contrast to the EMG/EMG correlations, correlations between EEG signals existed only over short durations that did not exceed 100 ms.
Finally, we found cross-correlation functions between EEG and EMG signals. We suggest that low correlation coefficients between EEG and EMG activities may be explained by an abundance of EEG signals unrelated to low-level motor parameters and by noncortical sources of a trial-to-trail variability of spinal motoneuron activity even though the subjects performed a stereotypical handwriting task.