S Ören Laue
email: soeren@mpi-inf.mpg.de

GEOMETRIC SET COVER AND HITTING SETS FOR POLYTOPES IN R 3

Keywords: Subject Classification: F.2.2, G.2.1 Computational Geometry, Epsilon-Nets, Set Cover, Hitting Sets

Suppose we are given a finite set of points P in R 3 and a collection of polytopes T that are all translates of the same polytope T . We consider two problems in this paper. The first is the set cover problem where we want to select a minimal number of polytopes from the collection T such that their union covers all input points P . The second problem that we consider is finding a hitting set for the set of polytopes T , that is, we want to select a minimal number of points from the input points P such that every given polytope is hit by at least one point.

We give the first constant-factor approximation algorithms for both problems. We achieve this by providing an epsilon-net for translates of a polytope in R 3 of size O( 1 ǫ ).

Introduction

Suppose we are given a set of n points P in R 3 and a collection of polytopes T that are all translates of the same polytope T . We consider two problems in this paper. The first is the set cover problem where we want to select a minimal number of polytopes from the collection T such that their union covers all input points P . The second problem that we consider is finding a hitting set for the set of polytopes T , that is, we want to select a minimal number of points from the input points P such that every given polytope is hit by at least one point.

Both problems, the set cover problem and the hitting set problem which are in fact dual to each other are very fundamental problems and have been studied intensively. In a more general setting, where the sets could be arbitrary subsets, both problems are known to be NP-hard, in fact they are even hard to approximate within o(log n) [START_REF] Lund | On the hardness of approximating minimization problems[END_REF]. Even when the sets are induced by geometric objects it is widely believed that the corresponding set cover problem as well as the hitting set problem are NP-hard. Several geometric versions of these problems were even proven to be hard to approximate. Hence, we are looking for algorithms that approximate both problems. We give the first constant-factor approximation algorithms for the set cover problem and the hitting set problem for translates of a polytope in R 3 . The central idea to our approximation algorithms are small epsilon-nets.

A set of elements P (also called points) along with a collection T of subsets of P (also called ranges) is in general called a set system (P, T ) and for geometric settings also known as range spaces. One essential characteristic of these set systems is the Vapnik-Chervonenkis dimension, or VC-dimension [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probability[END_REF]. The VC-dimension is the cardinality of the largest subset A ⊆ P for which {T ∩ A : T ∈ T } is the powerset of A. If the set A is finite, we say that the set system (P, T ) has bounded VC-dimension, otherwise we say the VC-dimension of (P, T ) is unbounded. For instance, the set system induced by translates of a polytope has VC-dimension three as well as the set system induced by halfspaces in R 2 . A set N ⊆ P is called an epsilon-net for a given set system (P, T ) if N ∩ T = ∅ for every subset T ∈ T for which T ≥ ǫ • P . In other words, an epsilon-net is a hitting set for all subsets T ∈ T whose cardinality is an ǫ-fraction of the cardinality of the input point set P .

It is known that there exist epsilon-nets of size O d ǫ log d ǫ for any set system of VCdimension d [START_REF] Blumer | Learnability and the vapnik-chervonenkis dimension[END_REF][START_REF] Komlós | Almost tight bounds for epsilon-nets[END_REF]. This bound is in fact tight for arbitrary set systems as there exist set systems that do not admit epsilon-nets of size less than this bound [START_REF] Pach | Some new bounds for epsilon-nets[END_REF]. Such an epsilon-net can be simply found by random sampling [START_REF] Matousek | Lectures on Discrete Geometry[END_REF].

However, for special set systems that are induced by geometric objects there do exist epsilon-nets of smaller size, namely of size O( 1 ǫ ). It has been shown by Pach and Woeginger [START_REF] Pach | Some new bounds for epsilon-nets[END_REF] that halfspaces in R 2 and translates of polytopes in R 2 admit epsilon-net of size O( 1 ǫ ). Matoušek et al. [START_REF] Matoušek | How to net a lot with little: Small epsilon-nets for disks and halfspaces[END_REF] gave an algorithm for computing small epsilon-nets for pseudodisks in R 2 and halfspaces in R 3 . The result for halfspaces in R 3 also follows from a more general statement by Matoušek [START_REF] Matoušek | Reporting points in halfspaces[END_REF].

Among other reasons for finding epsilon-nets of small size is the fact that an epsilon-net of size g(ǫ) immediately implies an approximation algorithm for the corresponding hitting set with approximation guarantee of O(g(1/c)/c), where c denotes the optimal solution to the hitting set [START_REF] Pach | Combinatorial Geometry[END_REF]. This means, that for arbitrary set systems of fixed VC-dimension we have an algorithm for the hitting set problem with approximation O(log c). And for set systems that admit epsilon-nets of size O(1/ǫ) we get an approximation algorithm to the hitting set problem with constant approximation guarantee.

Clarkson and Varadarajan [START_REF] Clarkson | Improved approximation algorithms for geometric set cover[END_REF] developed a technique that connects the complexity of a union of geometric objects to the size of the epsilon-net for the dual set system. Using this result, they are able to develop, among other approximation algorithms for geometric objects in R 2 , a constant-factor approximation algorithm for the set cover problem induced by translates of unit cubes in R 3 .

We extend their result to not only the set cover problem but also the hitting set problem for arbitrary translates of a polytope in R 3 . We do not require the polytope to be convex or fat. This is the first constant-factor approximation algorithm for these two problems. We achieve this by giving an epsilon-net for translates of a polytope in R 3 of size O( 1 ǫ ). We reduce the problem of finding epsilon-nets for translates of a polytope to a family of non-piercing objects in R 2 and then generalize the epsilon-net finder for pseudo-disks of Matoušek et al. [START_REF] Matoušek | How to net a lot with little: Small epsilon-nets for disks and halfspaces[END_REF] to our setting.

The set cover problem which is studied by Hochbaum and Maass [START_REF] Hochbaum | Approximation schemes for covering and packing problems in image processing and vlsi[END_REF] where one is allowed to move the objects is fundamentally different. They give a PTAS for their problem.

Small Epsilon-Nets for Polytopes in R 3

Let P be a set of n points in R 3 and let T be a family of polytopes that are all translates of the same bounded polytope T 0 . We want to find a set of polytopes of minimal cardinality among the collection T that covers all input points P . First, we find a small epsilon-net for this set system and use this later for the constant-factor approximation of the hitting set problem. Finally, we show how this then can be translated into a solution for the set cover problem.

Throughout this paper we denote by T the polytope as well as the subset of points from P that T covers and by T the family of polytopes as well as the corresponding family of subsets of P . This will make the paper easier to read and it will be clear from the context whether we talk about the geometric object or the corresponding set of points.

1.1. From Polytopes in R 3 to Non-Piercing Objects in R 2
So given such a set system (P, T ) we want to find an epsilon-net for it, i.e. we are looking for a set N ⊆ P such that every subset of points T ∈ T with T ≥ ǫ • P is stabbed by at least one point from N .

We can cut the polytope T into, lets say k polytopes T 1 , T 2 , . . . , T k . If the polytope T contains ǫn input points then one of the polytopes T 1 , T 2 , . . . , T k must contain at least ǫ k • n input points. Hence, in order to find an ǫ-net for the set system (P, T ) induced by translates of T , it suffices to find ǫ k -net for the set systems induced by the translates of T 1 , T 2 , . . . , T k . Following this reasoning we can reduce our problem for finding an epsilon-net for the set system induced by translates of arbitrary polytopes to translates of convex polytopes by cutting the possibly non-convex polytope into a set of convex polytopes. Note that the number of these convex polytopes only depends on the polytope T and hence is constant for fixed T .

Wlog. let T be from now on a convex polytope. We can place a cubical grid onto the space R 3 such that for any translate of T every cubical grid cell contains at most vertex of T . This can be achieved by making the grid fine enough. Clearly, the maximal number t of grid cells that can be intersected by T is bounded and only depends on T . Again, if T contains ǫn input points then at least one of the cells must contain at least ǫ t • n of the input points. Hence, we can restrict ourselves to finding epsilon-nets for translates of triangular cones where all input points lie in a cube in R 3 . This just adds a multiplicative constant to the size of the final epsilon-net.

The case when the cubical cell only contains a halfspace or the intersection of two halfspaces can be either seen as a special case of a cone or, in fact, be even treated separately in a much simpler way. The case of a translate of a halfspace reduces to a one-dimensional problem an admits an epsilon-net of size 1 and the case of two intersecting halfspaces reduces to a problem on intervals which admits an epsilon-net of size O(1/ǫ).

In the following we will construct an epsilon-net for the set system (P, C) that is induced by translates of a triangular cone C.

Given a cone C, we call a set of points P in non-C-degenerate position if every translate of C has at most three points of P on its boundary. We can always perturb the input points P in such a way that they are in non-C-degenerate position and the collection of subsets of the form P ∩ C T where C T is a translate of C does not decrease [START_REF] Edelsbrunner | On the number of line separations of a finite set in the plane[END_REF]. Hence, we can restrict ourselves on non-C-degenerate set of points P .

We place a coordinate system such that the input points all have z-coordinate greater than 0 and a ray r emitting from the apex of the cone C and lying entirely in the cone should intersect the plane z = 0. We refer to such a cone as a cone that opens to the bottom and the ray r as its internal ray. The following two definitions are helpful generalizations the lower envelope. Definition 1.1. Given a finite point set P and a triangular cone C that opens to the bottom consider the arrangement of all translates of C that have a point of P on its boundary but no point of P in its interior. The upper set of plane segments that can be seen from above is called the lower envelope of P with respect to cone C.

Figure 2 illustrates the definition of the lower envelope in the two-dimensional case. This definition is similar to the definition of alpha-shapes where the cone is replaced by a ball. We call all points that lie on the lower envelope with respect to cone C lower envelope points and denote this set by L. Definition 1.2. Let C be a triangular cone that opens to the bottom and let P ⊆ R 3 be a finite set of points in non-C-degenerate position. Let C ′ be a cone that is flatter that C by small δ and such that it contains C and the combinatorial structure of P and C ′ is the same as for P and C. See figure 3 for an illustration. Then, the lower envelope of P with respect to C ′ is called the flattened lower envelope of P with respect to cone C.

Such a cone C ′ always exists for a finite point set that is in non-C-degenerate position. From now on we will abbreviate the term lower envelope with respect to cone C by lower envelope since we will throughout this paper only talk about the same cone C. The flattened lower envelope can be basically seen as a slightly flattened version of the lower envelope.

The next lemma shows that we can reduce the problem of finding an epsilon-net with respect to cones of arbitrary point sets to lower envelope points.

Lemma 1.3. If for every finite point set P ′ ⊆ R 3 of lower envelope points in non-Cdegenerate position there exists an epsilon-net with respect to translates of a cone C of size s(ǫ) then there exists an epsilon-net with respect to translates of a cone C of size 3s(ǫ) for every finite point set P ⊆ R 3 in non-C-degenerate position. . Proof. Let P ⊆ R 3 be such a finite point set in non-Cdegenerate position and let C denote the cone. Let L denote the set of lower envelope points. Let L = P \ L be the set of all non-lower envelope points. We project all non-lower envelope points L along the internal ray r of cone C onto the flattened lower envelope (cf. figure 4). We denote the projection of a point p by p ′ . Let P ′ be union of the projected points and L. Clearly, P ′ is a set of lower envelope points in non-C-degenerate position.

Suppose we have an epsilon-net N ′ for this point set P ′ . From this epsilon-net N ′ we will construct an epsilonnet N for the original point set P . If a point from the set L is in the epsilon-net N ′ , we also add it to the epsilon-net N for P . If however, a projected point p ′ is in N ′ then we add to N the three points p 1 , p 2 and p 3 from the lower envelope L that determine the cone C on whose boundary also p ′ lies. Note that whenever an arbitrary cone contains the point p ′ then it has to contain one of the three points p 1 , p 2 or p 3 .

We have the following two properties:

(1) If a cone contains at least ǫn points from the set P then it contains at least ǫn points from the set P ′ . (2) If a cone contains a point from the epsilon-net N ′ for P ′ then the cone contains a point from the epsilon-net N for P . Both properties prove that the set N is indeed an epsilon-net for P .

The preceding lemma assures that we can restrict ourselves on a finite set of lower envelope points in non-C-degenerate position. For such a set system we will now construct a corresponding set system of points in the plane and a collection of regions in the plane. Definition 1.4. Let C be a cone and let P ′ be a finite set of lower envelope points in non-C-degenerate position and let C be a collection of translates of C. We define a projection τ from the flattened lower envelope onto the plane z = 0 by projecting each point along the internal ray r. Let the projection of all points p ′ ∈ P ′ which all lie on the be denoted as the set S. For each cone of the collection the image of the intersection of the cone with the flattened lower envelope is an object D ⊆ R 2 and the family C of cones induces a family of objects which we will denote by D.

Using the flattened lower envelope instead of the lower envelope avoids degeneracy. The intersection of an arbitrary cone with the flattened lower envelope is always a collection of line segments. Furthermore, it makes everything continuous in the sense that if a cone is moved continuously in R 3 then the intersection of the cone with the flattened lower envelope moves continuously as well as its image of the projection τ . Note, that τ is injective.

Analogously, we call a set of points S ⊆ R 2 in non-D-degenerate position if every D ∈ D has at most three points on its boundary. We have the following lemma: Lemma 1.5. If for every finite point set S ⊆ R 2 in non-D-degenerate position there exists an epsilon-net with respect to the family of objects D produced by the projection τ of size s(ǫ) then there exists an epsilon-net with respect to cones of size s(ǫ) for every point set of lower envelope points P ′ ⊆ R 3 in non-C-degenerate position.

Proof. The proof follows easily from the fact that the image of a cone C under the projection τ contains exactly those points that are the image of the points that are contained in C.

We refer to a cone C as the corresponding cone of the object D = τ (C). We will prove a few useful properties of the so constructed set system (S, D).

Notice, that the intersection of two triangular cones is again a cone. Furthermore, the intersection of a possibly infinite family of triangular cones is either empty or again a triangular cone since all cones are closed. The intersection of the boundary of a cone with the flattened lower envelope is either empty or a set of line segments that form one simple closed cycle. Hence, the image of a cone under the projection τ is a closed and connected region whose boundary is a closed and connected cycle. In this subsection we will derive a few properties of the projection that are necessary to apply the algorithm of Matoušek et al. [START_REF] Matoušek | How to net a lot with little: Small epsilon-nets for disks and halfspaces[END_REF] for finding a small epsilon-net for pseudodisks. These properties also hold in general for any family of non-piercing objects with the additional property that for any three points there always exists an object that has these three points on its boundary. However the proofs are a bit more involved. Since this does not lie in the scope of this paper, we omit this here and focus only on the special family of non-piercing objects that is produced by the projection described above.

Consider the family of all cones that have p and q on its boundary. The intersection of all these cones is a cone C pq that has p and q on its boundary. Connect p and q by a Jordan curve E pq such that it lies entirely in the cone C pq and on the flattened lower envelope, for instance part of the boundary of C pq that intersects the flattened lower envelope. The image of E pq under the projection τ is a curve τ (E pq ) embedded in the plane. Definition 1.8. Let D be a family of non-piercing objects and let S ⊆ R 2 be a finite set of points. We call two points p, q ∈ R 2 D-Delaunay neighbors if there exists an object D ∈ D that has p and q on its boundary and no other point of S in its interior. The D-Delaunay graph of S, in short D-DT(S), is the graph that is embedded in the plane, has S as its vertex set and the edges τ (E pq ) between all D-Delaunay neighbors p and q.

Due to the definition of the D-Delaunay edge between two D-Delaunay neighbors p and q it is guaranteed that whenever a object D ∈ D contains p as well as q then it also must contain the D-Delaunay edge τ (E pq ). In the following we will prove that this D-Delaunay graph is in fact a triangulation of the vertex set S. Proof. First, we will prove that D-DT(S) is planar. Suppose otherwise, i.e. two edges τ (E pq ) and τ (E rs ) intersect each other in the plane. Since the cone C pq does not have any point in its interior and C rs also does not have any point in its interior and since each of these cones has at most 3 points on its boundary the objects τ (C pq ) and τ (C rs ) would have to pierce each other, see figure 6 for an illustration. Here, it is actually essential, that the set S is in non-D-degenerate position. Thus, the graph is planar.

The graph D-DT(S) itself consists of an outer face which is defined by cones of the lower envelope that have at most 2 points on their boundary and all other faces are triangles defined by the cones of the lower envelope that have exactly three points on its boundary. Suppose an inner face F is not bounded by a triangle. Then, one can place the apex of a cone in such a way onto the flattened lower envelope such that its image under the projection τ is a point which lies inside this face F . By moving the cone upward one can ensure that the cone will finally have three points on its boundary whose image under the projection τ are three vertices of the face F but no point in its interior. Hence, the face F must be bounded by a triangle. Hence, D-DT(S) is a triangulation of the set S.

We call the points of S that lie define the outer face the convex hull of S with respect to cone C and we denote it by conv C (S). It is a generalization of the standard convex hull and we will make use of it later. For a standard triangulation one requires that the outer face is determined by the convex hull. Here, we replaced the standard convex hull by the convex hull with respect to cone C. This is the appropriate generalization that we need. Lemma 1.10. Let D be an object produced by the projection τ . The subgraph G of D-DT(S) induced by the points of S that lie in D is connected.

Proof. We prove the connectivity using induction over the number of points that lie in D. If D contains at most 2 points that it must be connected by definition and the fact that we can slide down the corresponding cone until both points lie on the boundary. So lets assume that every object D that contains at most k points from the set S induces a connected subgraph G. Now consider an object D that contains k + 1 points of S. Consider the cone that is the intersection of all cones that contain exactly those k + 1 points. This cone has exactly three points on its boundary. We can move the cone by a small δ in such a way that each of the three points can be excluded separately. As all of these induced graphs are connected by induction hypothesis, the whole subgraph induced by D must be connected.

We need two more lemmas. Both lemmas basically rely on the fact that projection τ is continuous. Proof. Let C be the corresponding cone of D. If we move C upward along the internal ray r by a small δ then the corresponding object D ′ of this cone will satisfy [START_REF] Assouad | Densité et dimension[END_REF]. On the other hand, if we move the cone C downward along the ray r by a small δ then the corresponding object D ′ will satisfy (2).

Lemma 1.12. Let S be a finite point set in non-D-degenerate position, let (p, q) be a D-Delaunay edge in D-DT(S). Then, there exists an object D with p and q on its boundary and with S ∩ D = {p, q}.

Proof. Let D be the object that assures that p, q is a D-Delaunay edge, i.e. D has p and q on its boundary. Since the point set S is in non-D-degenerate position D has at most three points on its boundary. If D has exactly two points on its boundary we are done. So lets assume that D has exactly three points on its boundary. Let C be the corresponding cone of D and let the corresponding points of p and q be p ′ ∈ R 3 and q ′ ∈ R 3 . Neither p ′ nor q ′ can lie on the intersection of two of the defining planes of cone C because otherwise the cone could still be moved in an upward direction such that all three points still lie on the boundary until the cone hits a fourth point. But this would mean that the point set was in C-degenerate position. Hence, p ′ and q ′ lie in the interior of two of the plane segments of cone C. If we now move the cone C downward by a small δ such that it still touches p ′ and q ′ then the corresponding object of this cone will only have p and q on its boundary.

Having these properties, we can basically directly apply the algorithm for finding an epsilon-net for pseudo-disks from [START_REF] Matoušek | How to net a lot with little: Small epsilon-nets for disks and halfspaces[END_REF]. We will describe the algorithm here and prove its correctness for our setting.

We are given a finite point set S in non-D-degenerate position and we want to find a subset N ⊆ S of size O(1/ǫ) that stabs any object D that contains at least ǫn points of S.

Let δ = ǫ/6. First, let S 1 , . . . , S j be pairwise disjoint subsets of S with the following properties: Each S i contains δn points, their union contains the convex hull of S with respect to cone C, i.e. conv C (S) ⊆ 1≤i≤j S i and each S i is representable by S ∩ τ (C i ) for an appropriate cone C i . Such sets can be easily constructed by repeatedly biting off points from conv C (S) with a suitable cone C i . Notice, that all these objects D i = τ (C i ) belong to the collection D.

Next, find a maximal pairwise disjoint collection S j+1 , . . . , S k of subsets of the remaining points S \ 1≤i≤j S i satisfying S i = S ∩ D i for some object D i and each subset containing δn points. Obviously, there are at most 1/δ + 1 many subsets S i in total. For an illustration we refer to figure 7. We assign all points in S i the color i and call all other points colorless. Let S be the set of all colored points. Note, that if an object contains only colorless points then it contains less that δn points, since the collection of subsets S i was maximal.

Let G be the D-Delaunay graph of the set of colored points S, i.e. G = DT( S). G is indeed a triangulation (cf. lemma 1.9). In this graph we call a triangle uni-colored, bi-colored or tri-colored depending upon the number of colors its vertices have. In a similar way we call edges uni-colored or bi-colored. We call a maximal connected chain of bi-colored triangles in G sharing bi-colored edges a corridor (cf. figure 8). Since the graph G is planar and each of the induced subgraphs G ∩ D i is connected according to lemma 1.10 the number of such corridors is at most 3k -6 ( [START_REF] Matoušek | How to net a lot with little: Small epsilon-nets for disks and halfspaces[END_REF]). All colorless points are contained in the corridors and the tri-colored triangles because any uni-colored triangle is contained it its color-defining object. We break each corridor R into a minimum number of sub-corridors, i.e. sub-chains of the chain that forms R, so that each sub-corridor contains at most δn colorless points. Since there are less than n colorless points and since the total number of corridors is 3k -6 the total number of sub-corridors is O(1/δ).

Each sub-corridor is bounded by two chains of uni-colored edges which we call sides and by two bi-colored edges which we call ends of the sub-corridor. The endpoints of the sides are called corners. Let N ⊆ S be the set of all corners of all sub-corridors. Since each sub-corridor has at most 4 corners the size of N is O(1/ǫ). The set N is an epsilon-net for the set of non-piercing objects D.

The proof that N is indeed an epsilon-net relies in principle on the fact that the collection D are non-piercing objects and follows along the lines of [START_REF] Matoušek | How to net a lot with little: Small epsilon-nets for disks and halfspaces[END_REF].

Proof. Let D be an object that has no points of S on its boundary (cf. lemma 1.11) and assume that D does not contain any points from N . The theorem is proven when we can show that D then contains less than ǫn points of S. If D contains no colored point then we are done, because the sets S i were a maximal. Hence, D must contain at least one colored point. If it contains two colored points, lets say z 1 of color 1 and z 2 of color 2, we can draw the following picture: Let D 1 be the color defining object of color 1 and D 2 the color defining object of color 2. Then D intersects D 1 and D 2 but cannot pierce them. The area between D 1 and D 2 is a sub-corridor whose ends we denote by (a 1 , a 2 ) and (b 1 , b 2 ). Lemma 1.12 assures that there is an object D a that has a 1 and a 2 on its boundary and there is an object D b that has b 1 and b 2 on its boundary. Since D also does not contain any point from N which are the corners of the sub-corridors, i.e. it does not contain a 1 , a 2 , b 1 or b 2 and since D and D a as well as D and D b are non-piercing it must lie between two ends of one sub-corridor. See figure 9 for an illustration. Now, as all objects D 1 , D 2 , D a and D b contain at most δn points and the sub-corridor also contains at most δn points D can contain at most 5 • δn = 5/6ǫn < ǫn points of S.

The case where D only contains points of one color and colorless points is very similar. There is basically only one setup and it is depicted in figure 10. Arguing as above it easy to see in this case that D cannot contain more than 4 • δn < ǫn points from S. Together with lemma 1.3 and lemma 1.5 this immediately implies our main theorem Theorem 1.14. Given a finite point set P ⊆ R 3 and a polytope T ⊆ R 3 . The set system (P, T ) induced by a set of translates of polytope T admits an epsilon-net of size O(1/ǫ).

From Epsilon-Nets to Hitting Sets

In this section we will describe a constant factor approximation algorithm to the hitting set problem using the epsilon-net of size O(1/ǫ) from the previous section. Recall that in the hitting set problem we are given a set of points P ∈ R 3 and a set polytopes that are all translates of the same polytope and we would like to select a subset H ⊆ P of the input points of minimal cardinality such that every polytope is stabbed by a point in H. We denote the corresponding set system by (P, T ). The fractional hitting set problem is a relaxation of the original hitting set problem and is defined by the following linear program:

min p∈P x(p) (2.1) s. t. ∀T ∈ T p∈T x(p) ≥ 1 (2.2) ∀p ∈ P x(p) ≥ 0 (2.3)
Let OPT denote the optimal size of the hitting set and OPT * the optimal value of the fractional hitting set problem. It is known that the integrality gap is constant for set systems that admit an epsilon-net of size O(1/ǫ) [START_REF] Pach | Combinatorial Geometry[END_REF].

Let w : P → R ≥0 be a weight function for the set P . We define the weight w(A) of a subset A ⊆ P to be the sum of the weights of the elements of A. The weighted version of an epsilon-net is as follows: Definition 2.1. Consider a set system (P, T ) and a weight function w : P → R ≥0 . A set H ⊆ P is called an epsilon-net with respect to w if H ∩ R = ∅ for every subset T ∈ T for which w(T ) ≥ ǫ • w(S).

There are algorithms that compute a hitting set provided one has an epsilon-net finder. The core idea to all these algorithms is to find a weight function w : P → R ≥0 that assigns weights to the elements of P and finds an appropriate ǫ such that every set in T has weight at least ǫ • w(S). Once such weights are found it is then obvious that an epsilon-net to this set system is automatically a hitting set.

The algorithm given by Brönnimann and Godrich [START_REF] Brönnimann | Almost optimal set covers in finite vc-dimension: (preliminary version)[END_REF] computes these weights iteratively. Initially, all elements have weight 1. Then, in each iteration an epsilon-net is computed and then checked whether it is also a proper hitting set. If not, i.e. there is a set which is not hit, then the weights of its elements are doubled. This is done until a hitting set is found. This algorithm can be seen as a deterministic analogue of the randomized natural selection technique used for instance by Clarkson [START_REF] Clarkson | Las vegas algorithms for linear and integer programming when the dimension is small[END_REF].

Another algorithm is by Even et al. [START_REF] Even | Hitting sets when the vc-dimension is small[END_REF]. Here, the weights of the elements and ǫ are directly found by the following linear program:

max ǫ (2.4) s. t. ∀T ∈ T w(T ) ≥ ǫ (2.5) p∈P w(p) = 1 (2.6) ∀p ∈ P w(p) ≥ 0 (2.7)
It suffices to approximate the solution to this linear problem. There are numerous algorithms that find an approximate solution to such a covering linear program efficiently [START_REF] Young | Randomized rounding without solving the linear program[END_REF][START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF].

One can reduce the problem of finding a weighted epsilon-net to the unweighted case. One just makes multiple copies of a point according to its assigned weight and it can be shown that the cardinality of this multiset can be bounded by 2n [START_REF] Clarkson | Improved approximation algorithms for geometric set cover[END_REF]. Hence, an ǫ 2 -net for this set system gives a hitting set for the original hitting set problem. Hence, we have Theorem 2.2. There exists a polynomial time algorithm that computes a constant-factor approximation to the hitting set problem for translates of polytopes in R 3 .

From Hitting Set to Set Cover

Definition 3.1. The dual set system of a set system (P, T ) is the set system (T , P * ) where P * = {T p : p ∈ P } and T p consists of all subsets of T that contain p.

Obviously, a set cover for the primal set system is a hitting set for the dual set system. Hence, in order to solve the set cover problem for a set system it suffices to solve the hitting set problem for the dual set system. For arbitrary set systems, the dual set system can be of quite different structure. In general it is only known that the VC-dimension of the dual set system is less than 2 d+1 , where d is the VC-dimension of the primal set system [START_REF] Assouad | Densité et dimension[END_REF].

However, we observe that if the set system is induced by translates of a polytope, then the dual is again induced by translates of a polytope. To see this, let (P, T ) be the primal set system. One just reduces each polytope T ∈ T to a point, for instance each to its lowest vertex. Let this be the set P ′ . Then, replace each point of P by a translate of the polytope T ′ which is the inversion of T in a point. One easily verifies that the so constructed set system (P ′ , T ′ ) of points P ′ and collection of translates of polytope T ′ is indeed equivalent to the dual (T , P * ). This holds in fact for all R d . Hence, we can find a constant-factor approximation to the set cover problem for translates of a polytope in R 3 in polynomial time. This brings us to our final theorem Theorem 3.2. There exists a polynomial time algorithm that computes a constant-factor approximation to the set cover problem for translates of polytopes in R 3 .

Conclusions and Open Problems

In this paper we have given the first constant-factor approximation algorithm for finding a set cover for a set of points in R 3 by a given collection of translates of a polytope as well as the first constant-factor approximation algorithm for the corresponding hitting set problem. We achieved this result by providing an epsilon-net of size O( 1 ǫ ) for the corresponding set system which is optimal up to a multiplicative constant. Eventhough we can approximate a unit ball in R 3 up to any given precision by a polytope, the corresponding question, whether there exists a constant-factor approximation algorithm for unit balls in R 3 still remains open.

Figure 1 Figure 1 :

 11 Figure 1: The cone C and its internal ray r.

Figure 2 :

 2 Figure 2: The lower envelope with respect to cone C, the corresponding cones are drawn dotted.

Figure 3 :

 3 Figure 3: The flattened lower envelope with respect to cone C, lower envelope is drawn dotted.

Figure 4 :

 4 Figure 4: The projection of points onto flattened lower envelope.

Figure 5 :.Definition 1 . 6 .Lemma 1 . 7 .

 51617 Figure 5: A set of nonpiercing objects

Lemma 1 . 9 .Figure 6 :

 196 Figure 6: Two intersecting D-Delaunay edges and their defining objects .Proof. First, we will prove that D-DT(S) is planar. Suppose otherwise, i.e. two edges τ (E pq ) and τ (E rs ) intersect each other in the plane. Since the cone C pq does not have any point in its interior and C rs also does not have any point in its interior and since each of these cones has at most 3 points on its boundary the objects τ (C pq ) and τ (C rs ) would have to pierce each other, see figure6for an illustration. Here, it is actually essential, that the set S is in non-D-degenerate position. Thus, the graph is planar.The graph D-DT(S) itself consists of an outer face which is defined by cones of the lower envelope that have at most 2 points on their boundary and all other faces are triangles defined by the cones of the lower envelope that have exactly three points on its boundary. Suppose an inner face F is not bounded by a triangle. Then, one can place the apex of a cone in such a way onto the flattened lower envelope such that its image under the projection τ is a point which lies inside this face F . By moving the cone upward one can ensure that the cone will finally have three points on its boundary whose image under the projection τ are three vertices of the face F but no point in its interior. Hence, the face F must be bounded by a triangle. Hence, D-DT(S) is a triangulation of the set S.

Lemma 1 . 11 .

 111 Let S be a finite point set.

( 1 ) 2 )

 12 For any object D ∈ D, there exists an object D ′ ∈ D with S ∩D ′ = S ∩int D ′ = S ∩D. (For any object D ′ ∈ D, there exists an object D ∈ D with S ∩ D ′ = S ∩ int D ′ = S ∩ int D.

Figure 7 :RFigure 8 :

 78 Figure 7: The sets S i and the convex hull conv C (S) with respect to cone C. The D-Delaunay triangulation is drawn dotted.

2 Figure 9 : 2 Figure 10 :

 29210 Figure 9: The case where D contains colored points of at least two colors.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Acknowledgements

The author would like to thank Nabil H. Mustafa and Saurabh Ray for useful discussion on the topic and an anonymous referee for pointing out an error in a preliminary version of this paper.

This work was supported by the Max Planck Center for Visual Computing and Communication (MPC-VCC) funded by the German Federal Ministry of Education and Research (FKZ 01IMC01). c S ören Laue

CC


Angsheng Li
email: angsheng@ios.ac.cn

Mingji Xia

A THEORY FOR VALIANT'S MATCHCIRCUITS (EXTENDED ABSTRACT)

Keywords: Subject Classification: F.1.1 Pfaffian, Matchgate, Matchcircuit

The computational function of a matchgate is represented by its character matrix. In this article, we show that all nonsingular character matrices are closed under matrix inverse operation, so that for every k, the nonsingular character matrices of k-bit matchgates form a group, extending the recent work of Cai and Choudhary [1] of the same result for the case of k = 2, and that the single and the two-bit matchgates are universal for matchcircuits, answering a question of Valiant [4].

Introduction

Valiant [4] introduced the notion of matchgate and matchcircuit as a new model of computation to simulate quantum circuits, and successfully realized a significant part of quantum circuits by using this new model. Valiant's new method organizes certain computations based on the graph theoretic notion of perfect matching and the corresponding algebraic object of the Pfaffian. This leaves an interesting open question of characterizing the exact power of the matchcircuits. To solve these problems, a significant first step would be a better understanding the structures of the matchgates and the matchcircuits, to which the present paper is devoted.

In [6], Valiant introduced the notion of holographic algorithm, based on matchgates and their properties, but with some additional ingredients of the choice of a set of linear basis vectors, through which the computation is expressed and interpreted.

Matchgates and their character matrices have some nice properties, which have already been extensively studied. In [1], Cai and Choudhary showed that a matrix is the character matrix of a matchgate if and only if it satisfies all the useful Grassmann-Plücker identities, and all nonsingular character matrices of two bits matchgates form a group.

In the present paper, we show that for every k, all the nonsingular character matrices of k-bit matchgates form a group, extending the result of Cai and Choudhary of the same result for the case of k = 2.

Furthermore, we show that every matchcircuit based on k-bit matchgates for k > 2 can be realized by a series of compositions of either single bit or two bits matchgates. This result answers a question raised by Valiant in [4]. The result is an analogy of the quantum circuits in the matchcircuits [3].

We organize the paper as follows. In section 2, we outline necessary definitions and background of the topic. In section 3, we state our results, and give some overview of the proofs. In section 4, we establish our first result that for every k, all nonsingular k-bit character matrices form a group. In section 5, we prove the second result that level 2 matchgates are universal for matchcircuits.

Definitions

Graphs and Pfaffian

Let G = (V, E, W ) be a weighted undirected graph, where V = {1, 2, . . . , n} is the set of vertices each represented by a distinct positive integer, E is the set of edges and W is the set of weights of the edges. We represent the graph by a skew-symmetric matrix M , called the skew-symmetric adjacency matrix of G, where

M (i, j) = w(i, j) if i < j, M (i, j) = -w(i, j) if i > j, and M (i, i) = 0.
The Pfaffian of an n × n skew-symmetric matrix M is defined to be 0 if n is odd, 1 if n is 0, and if n = 2k where k > 0 then it is defined by

Pf (M ) = π ǫ π w(i 1 , i 2 )w(i 3 , i 4 ) . . . w(i 2k-1 , i 2k ), where • π = [i 1 , i 2 , . . . , i 2k ] is a permutation on [1, 2, . . . , n],
• the summation is over all permutations π, where i 1 < i 2 , i 3 < i 4 , . . . , i 2k-1 < i 2k and i 1 < i 3 < . . . < i 2k-1 , • ǫ π is the sign of the permutation π, or equivalently, ǫ π is the sign or parity of the number of overlapping pairs, where a pair of edges (i 2r-1 , i 2r ), (i 2s-1 , i 2s ) is

overlapping iff i 2r-1 < i 2s-1 < i 2r < i 2s or i 2s-1 < i 2r-1 < i 2s < i 2r .
A matching is a subset of edges such that no two edges share a common vertex. A vertex is said to be saturated if there is a matching edge incident to it. A perfect matching is a matching which saturates all vertices. There is a one-to-one correspondence between the monomials in the Pfaffian and the perfect matchings in G.

If M is an n × n matrix and A = {i i , . . . , i r } ⊆ {1, . . . , n}, then M [A] denotes the matrix obtained from M by deleting the rows and columns of indices in A. The Pfaffian Sum of M is a polynomial over indeterminates λ 1 , λ 2 , . . . , λ n defined by

PfS(M ) = A ( i∈A λ i )Pf(M [A])
where the summation is over the 2 n subsets of {1, . . . , n}. There is a one-one correspondence between the terms of the Pfaffian sum and the matchings in G. We consider only instances such that each λ i is fixed to be 0 or 1. In this case, Pfaffian Sum is a summation over all matchings that match all nodes with λ i = 0. It is well known that both the Pfaffian and the Pfaffian Sum are computable in polynomial time.

Matchgate

A matchgate Γ, is a quadruple (G, X, Y, T ), where G = (V, E, W ) is a graph, X ⊆ V is a set of input nodes, Y ⊆ V is a set of output nodes, and T ⊆ V is a set of omittable nodes such that X, Y and T are pairwise disjoint. Usually the numbers of nodes in V are consecutive from 1 to n = |V | and X, Y have minimal and maximal numbers respectively. Whenever we refer to the Pfaffian Sum of a matchgate fragment, we assume that λ i = 1, if i ∈ T , and 0 otherwise. Each node in X ∪ Y is assumed to have exactly one incident external edge. For a node in X, the other end of the external edge is assumed to have index less than the index for any node in V , and for a node in Y , the other end node has index greater than that for every node in

V . If k = |X| = |Y |, then Γ is called k-bit matchgate.
A matchgate is called a level k matchgate, if it is an n-bit matchgate for some n ≤ k. If a matchgate only contains input nodes, output nodes and one ommitable node, then it is called a standard matchgate.

We define, for every Z ⊆ X ∪ Y , the character χ(Γ, Z) of Γ with respect to Z to be the value µ(Γ, Z)PfS(G -Z), where G -Z is the graph obtained from G by deleting the vertices in Z together with their incident edges, and the modifier µ(Γ, Z) ∈ {-1, 1} counts the parity of the number of overlaps between matched edges in G -Z and matched external edges. We assume that all the nodes in Z are matched externally. By definition of the modifier, it is easy to verify that µ(Γ, Z) = µ(Γ, Z ∩ X)µ(Γ, Z ∩ Y ), and that if X = {1, 2, . . . , k} and Z ∩ X = {i 1 , i 2 , . . . , i l }, then µ(Γ, Z ∩ X) = (-1) l j=1 (i j -j) . The character matrix χ(Γ) is defined to be the 2 |X| × 2 |Y | matrix such that entry

(i 1 i 2 . . . i k , i n i n-1 . . . i n-k+1 ) is χ(Γ, X ′ ∪ Y ′ ), where X ′ = {j ∈ X|i j = 1}, Y ′ = {j ∈ Y |i j = 1} and i 1 i 2 . . . i k , i n i n-1 .
. . i n-k+1 are binary expression of numbers between 0 and 2 k -1. We also use (X ′ , Y ′ ) to denote this entry. We call an entry (X ′ , Y ′ ) edge entry, if

0 < |(X -X ′ ) ∪ (Y -Y ′ )| ≤ 2.
Throughout the paper, we identify a matchgate and its character matrix. An easy but useful fact is that for every k, the 2 k × 2 k unit matrix is a character matrix.

Properties of character matrix

We introduce several properties of character matrices, which will be used in the proof of our results.

Theorem 2.1 ([4]

). If A and B are character matrices of size 2 k × 2 k , then AB is a character matrix.

Theorem 2.2 ([4]

). Given any matchgate Γ there exists another matchgate Γ ′ that has the same character as Γ and has an even number of nodes, exactly one of which is omittable.

Theorem 2.3 ([1]

). Let A be a 2 k × 2 l matrix. Then A is the character matrix of a k-input, l-output matchgate, if and only if A satisfies all the useful Grassmann-Plücker identities. This is a very useful characterization of the character matrices generalizing the characterization for a major part of all 2-input 2-output matchgates in [4]. The proof of this theorem implies the following:

Corollary 2.4 ([1]
). Let A be a 2 k × 2 l matrix whose right-bottom most entry is 1 satisfying all the useful Grassmann-Plücker identities. Then A is uniquely determined by its edge entries and A is the character matrix of a standard matchgate Γ containing k + l + 1 nodes (k input nodes, l output nodes and 1 omittable node).

Recently, Cai and Choudhary also showed that:

Theorem 2.5 ([1]). Let A be a 4 × 4 character matrix. If A is invertible, then A -1 is a character matrix.
Consequently, the nonsingular 4 × 4 character matrices form a group.

Matchcircuit

Given a matchgate Γ = (G, X, Y, T ), we say that it is even, if PfS(G -Z) is zero whenever Z = X ∪ Y has odd size, and odd if PfS(G -Z) is zero whenever |Z| is even.

Theorem 2.6 ([4], [1]). Consider a matchcircuit Γ composed of gates as in [4]. Suppose that every gate is:

(1) a gate with diagonal character matrix, (2) an even gate applied to consecutive bits x i , x i+1 , . . . , x i+j for some j, (3) an odd gate applied to consecutive bits x i , x i+1 , . . . , x i+j for some j, or (4) an arbitrary gate on bits x 1 , . . . , x j for some j. Suppose also that every parallel edge above any odd matchgate, if any, has weight -1 and all other parallel edges have weight 1. Then the character matrix of Γ is the product of the character matrices of the constituent matchgates, each extended to as many inputs as those of Γ.

From now on, whenever we say a matchcircuit, we mean that it satisfying the requirements in the above theorem. An example circuit is shown in Fig. 1, where the edges in a matchgate are not drown, and each node has index smaller than that of all nodes located to the right of the node. We call a matchcircuit is of level k, if it is composed of matchgates no more than k bits. The character matrix of a matchcircuit is defined by the same way as that of a matchgate except that there is no modifier µ.

The results and overview of the proofs

Theorem 3.1. For every k, the nonsingular 2 k × 2 k character matrices form a group under the matrix multiplication.

We will prove theorem 3.1 by induction on the size of matchgates. The proof proceeds as follows. Based on corollary 2.4, we observe that all 2 k × 2 k character matrices can be transformed to a special form 2 k × 2 k character matrices. This suggests the following: Definition 3.2. We say that a k-bit matchgate is a reducible matchgate, if the bottom pair of nodes k and nk + 1 are connected by a weight 1 edge, and there is no other edge incident to any of the nodes k and nk + 1.

The character matrix of a reducible matchgate is called a reducible character matrix.

By corollary 2.4, a character matrix B is a reducible character matrix if it satisfies the following:

(1)

B 2 k -1,2 k -1 = B 2 k -2,2 k -2 = 1.
(2) All the edge entries in the last two columns and the last two rows are 0 except for

B 2 k -2,2 k -2 .
Firstly we prove that if the k-bit nonsingular character matrices are closed under matrix inverse operation, then so are the (k + 1)-bit nonsingular reducible character matrices .

Secondly, we introduce some elementary nonsingular matchgates so that every nonsingular 2 k × 2 k character matrix can be transformed to a reducible character matrix by multiplying with the character matrices of the elementary matchgates.

This transformation is realized by four phases as follows. Starting from A = A (0) , we need the following: Phase T1 (A (0) ⇒ A [START_REF] Cai | On the Theory of Matchgate Computations[END_REF] ). Turn the right-bottom most entry to 1. Phase T2 (A [START_REF] Cai | On the Theory of Matchgate Computations[END_REF] ⇒ A [START_REF] Murota | Matrices and Matroids for Systems Analysis[END_REF] ). Turn the edge entries in the last row and column to 0's, while keeping the right-bottom most entry 1. Phase T3 (A [START_REF] Murota | Matrices and Matroids for Systems Analysis[END_REF] ⇒ A [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF] ). Turn the entry A

(2) 2 k -2,2 k -2 to 1, while keeping the right-bottom most entry 1 and the edge entries in the last row and column 0's. Phase T4 (A [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF] ⇒ A [START_REF] Valiant | Quantum circuits that can be simulated classically in polynomial time[END_REF] ). Turn the edge entries in the row 2 k -2 and column 2 k -2 to 0's, while keeping the last two diagonal entries 1's and the edge entries in the last row and column 0's.

Each phase consists of several actions (or for simplicity, steps). In each step, either the positions of entries are changed, or the values of some entries are changed.

An action is defined to be the multiplication of a character matrix with an elementary character matrix. The role of an action is to change some specific entries to be some fixed value 0 or 1. However, such an action will certainly injure other entries which are undesired.

The crucial observation is that an appreciate sequence of actions will gradually satisfy all the entries requirements. During the course of the transformation, once an entry requirement is satisfied by some action, it will never be injured again by the future actions. That is to say, an action may injure only the entries which have not been satisfied. This ensures that all the entries requirements will be eventually satisfied.

This describes the idea of the proof of theorem 3.1. The proof will also build an essential ingredient for our second result, the theorem below. Theorem 3.3. For every k > 2, if Γ is a matchcircuit composed of level k matchgates, then:

(1) Γ can be simulated by a level 2 matchcircuit ∆.

(2) A k-bit matchgate can be simulated by O(k 4 ) many single and two-bit matchgates.

And every matchcircuit Γ can be simulated by a level 2 matchcircuit in polynomial time.

Our proof of theorem 3.3 is a composition of the proof of theorem 3.1 and some more elementary matchgates. On the other hand, one could firstly prove theorem 3.3, then prove 3.1 by combining theorem 3.3 and theorem 2.5. However there are subtle difference between character matrices of matchgate and matchcircuit. Therefore, this approach needs additional technique.

Group property of the k-bit character matrices

In this section, we prove theorem 3.1. To proceed an inductive argument, we exploit the structure of the reducible character matrices which pave the way to the reductions.

Reducible matchgates

Lemma 4.1. Let ∆ 1 be a (k+1)-bit reducible matchgate, that is, the bottom edge (k+1, k+3) having weight 1 and there is no any other edge incident to any of the nodes k + 1 and k + 3. Let Γ 1 be the k-bit matchgate obtained from ∆ 1 by deleting the edge (k + 1, k + 3). Then:

(i) If ∆ 1 is invertible, so is Γ 1 . (ii) If χ(Γ 1 ) -1 is a character matrix, so is χ(∆ 1 ) -1 .
Proof. (Sketch) For (i). This holds because χ(∆ 1 ) is a block diagonal matrix after rearranging the order of rows and columns, and χ(Γ 1 ) is equal to one block. For (ii). We prove this by constructing the inverted matchgate ∆

2 (F 2 , W 2 , Z 2 , T 2 ) of ∆ 1 (F 1 , W 1 , Z 1 , T 1 ) from the inverted gate Γ 2 (G 2 , X 2 , Y 2 , T 2 ) of Γ 1 (G 1 , X 1 , Y 1 , T 1 ).
It suffices to prove that the composition of ∆ 1 and ∆ 2 has the unit matrix as its character matrix. See Fig. 2 for the intuition of the proof, while detailed verification will be given in the full version of the paper.

2: Example of k = 2. X 1 = {1, 2}, Y 1 = {6, 7}, T 1 = {4} X 2 = {8, 9}, Y 2 = {13, 14}, T 2 = {11}, W 1 = {1, 2, 3}, Z 1 = {5, 6, 7}, W 2 = {7, 8, 9}, Z 2 = {12, 13, 14}.

The transformation lemma

In this part, we construct the matchgates to realize the phases T1 -T4 prescribed in section 3, and show that every k-bit nonsingular character matrix can be transformed to a k-bit reducible character matrix by using the transformation.

The key point to the proof of the theorem is the following: Lemma 4.2. Let A be a 2 k ×2 k nonsingular character matrix. Then there exist nonsingular character matrices L s , . . . , L 2 , L 1 , R 1 , R 2 , . . . , R t for some s and t such that

L s • • • L 2 L 1 AR 1 R 2 • • • R t is a reducible character matrix.
Proof. Given a nonsingular character matrix A, we denote A by A (0) . We construct the matchgates to realize the four phases T1 -T4. We use A (i) to denote the character matrix obtained from A (i-1) by using phase Ti, where i = 1, 2, 3, 4. We start with A (0) , and define the transformation to be a series of actions, defined in section 3. In the discussion below, we will use A to denote the character matrix obtained so far in the construction from A (0) (or shortly, the current matrix).

The four phases proceed as follows. Phase T1: Suppose that Γ l is the k-bit matchgate such that the l-th pair of input-output nodes are connected by a path of length 2 on which each edge has weight 1, and each of the other pairs is connected by an edge of weight 1, and k +1 is the only unomittable node other than the input and output nodes. (See Fig. 3 (a)). Let C l denote the character matrix of Γ l . Suppose without loss of the generality that A I=i 1 i 2 ...i k ,J=j 1 j 2 ...j k = 0. Define

L 1 = 1≤l≤k,i l =0 C l , R 1 = 1≤l≤k,j l =0 C l .
It is easy to see that the right-bottom most entry, a say, of L 1 AR 1 is either A I,J or -A I,J by computing the PfS(G -X ∪ Y ) of the composed matchgate corresponding to

L 1 AR 1 . Let L 2 = 1 a E, and
A (1) = L 2 L 1 AR 1 .
Clearly L 2 is a character matrix, so is A [START_REF] Cai | On the Theory of Matchgate Computations[END_REF] , by theorem 2.1.

Phase T2: Phase T2 will change the edge entries in the last column and the last row to 0's. We first describe the actions for the column as follows.

Phase T2 for the last column:

We turn the edge entries in the last column to 0's one by one from bottom to top. To turn an edge entry (X ′ , 2 k -1) to zero, we need a row transformation applied to the current matrix A, which adds the multiplication of -b and the last row to row X ′ , where b is the value of entry (X ′ , 2 k -1) of the current matrix.

Therefore phase T2 for the last column consists of the following actions. In decreasing order of X ′ , for every edge entry (X ′ , 2 k -1), we have:

Action (X ′ , 2 k -1): Multiplying an elementary character matrix, L say, to the current character matrix A from the left side, where L is a character matrix satisfying that the diagonal entries are all 1's, and that

L I=X ′ ,2 k -1 = -b.
This makes some row transformations to the current matrix according to the nonzero entries other than the diagonal entries. The row transformation corresponding to L I=X ′ ,2 k -1 = -b is exactly the one that realizes the goal of this action. Now we formally construct the matchgate to realize the character matrix L as required in the action (X ′ , 2 k -1) above. The construction is divided into two cases depending on the size of X ′ as follows.

Case 1. X ′ = X -{i} for some i.

We use the matchgate with the following properties: (1) each input-output pair of the gate is connected by an edge of weight 1, and (2) it contains one more edge (i, t) to realize L, where t is the unique omittable node, and the weight of (i, t) is either b or -b ensuring L I,2 k -1 = -b. For intuition of the matchgate, a reader is referred to Fig. 3 (b).

Let (I ′ , J ′ ) be an arbitrary nonzero entry of L other than the diagonal entries. By the construction of the gate, we have that the i-th bit of I ′ and J ′ are 0 and 1 respectively, and that I ′ , and J ′ are identical on the j-th bit for every j = i. Hence I ′ < J ′ and I ′ ≤ I (recall that I = X ′ ). The action at entry (X ′ , 2 k -1) in this case actually makes the following row transformation: For each such pair (I ′ , J ′ ), row I ′ is added by the multiplication of L I ′ ,J ′ and row J ′ . Since I ′ ≤ I, all the edge entries (I 1 , 2 k -1) with I 1 > I have never been injured by the action in this case.

Case 2 X ′ = X -{i, j} for some i, j.

The character matrix L in this case is constructed by a similar way to that in case 1 above, using the matchgate in Fig. 3 (c).

The cost of the action in this case is similarly analyzed to that for case 1.

Recall that after phase T1, the right-bottom most entry is 1. The actions in both case 1 and case 2 of phase T2 above will never injure the last row of the matrix, so that the satisfaction of T1 is still preserved by the current state of the construction.

Phase T2 for the last row: The construction, and analysis for the actions is the same as that for the column case with the roles of rows and columns exchanged.

Therefore, the goal of T2 prescribed in section 3 has been realized. Phase T3: The goal of this phase is similar to that of phase T1, but different actions are needed. T3 consists of 2 actions. The first action moves a nonzero edge entry to position (2 k -1, 2 k -1), and the second one changes edge entry (2 k -1, 2 k -1) to 1. The actions proceed as follows.

Now we analyze the cost of the action. We first prove that it does not injure the edge entries in column 2 k -2 which have already been satisfied. The reason is similar to that in phase T2. Because I ′ ≤ X -{i}, the action only injures the rows with indices less than X -{i}.

The cost of the action is different from that in phase T2 in that it may affect the edge entries in the last column which have already been satisfied in phases T1 and T2. Because I ′ and J ′ contain the same number of 0's, which is at least 1, all the row changes made by the action always add a zero edge entry of the last column to another zero edge entry in the same column. Hence, it does not injure the satisfied entries in the last column. Additionally, it is obvious that the last two rows are preserved during the current action, so the left-bottom most entry, the edge entries in the last row and entry (2 k -2, 2 k -2) are all preserved.

Phase T4 for row 2 k -2: Similar actions to that in phase T4 for the column above can be applied to the row 2 k -2 to change its edge entries to 0's.

Therefore, T4 realizes its goal, at the same time, it preserves the satisfied entries in phases T1 -T3.

We have realized the phases T1 -T4 prescribed in section 3, by corollary 2.4, B is a reducible character matrix. The lemma follows.

Proof of theorem 3.1

Proof. We prove by induction on k that for every k, and every 2 k × 2 k character matrix A, if A is invertible, then A -1 is a character matrix.

The case for k = 1 is easy, the first proof was given by Valiant in [4]. Suppose by induction that the theorem holds for k -1. By lemma 4.2, there exist nonsingular character matrices L i and R j such that

B = L s • • • L 2 L 1 AR 1 R 2 • • • R t
is the character matrix of a reducible matchgate ∆. Let B ′ be the 2 k-1 × 2 k-1 character matrix of Γ constructed from ∆ by deleting the bottom edge.

Since A is invertible, so is B, and so is B ′ by lemma 4.1. By the inductive hypothesis, B ′-1 is a character matrix, so is B -1 by lemma 4.1.

By the choice of L i and R j , for all 1 ≤ i ≤ s and 1 ≤ j ≤ t, we have that

A -1 = R 1 R 2 • • • R t B -1 L s • • • L 2 L 1 . By theorem 2.1, A -1
is also a character matrix. This completes the proof of theorem 3.1.

We notice that the inductive argument in the proof of theorem 3.1 also gives a different proof for the result in the case of k = 2. Our method is a constructive, and uniform one. It may have some more applications.

Level 2 matchgates are universal

We introduce nine types of matchgates as our elementary gates. We use Γ a , . . . , Γ i , to denote the elementary level 2 matchgates corresponding to that in the following Fig. 4 We describe the elementary gates as follows. All edges in Γ a have weight 1. All edges connecting an input and an output node except for the edge in Γ f , and the diagonal edge in Γ g , are all of weight 1. The remaining edges take weights w.

Γ a makes a row (or column, when it is multiplied from right side) exchange, which is a special transformation, of the character matrix according to a bit flip on the label, and it is used to move a nonzero entry to the right-bottom most entry by the same way as that in the proof of theorem 2.3 in [1]. Γ b is used to realize cE, and to turn a nonzero entry to 1. Both Γ a and Γ b are only used in the first phase, i.e. T1, of the transformation. Intuitively, Γ c can exchange two consecutive bits, and it allows us to apply some other elementary gates to nonconsecutive bits. Γ d and Γ e are used in phase T2 to eliminate the edge entries in the last column and the last row. Γ c will be also used in phase T3 to move a nonzero edge entry to position (2 k -2, 2 k -2), in which case, Γ f will further turn this entry to 1. Γ g is used in phase T4 to eliminate the edge entries in the column 2 k -2 and row 2 k -2. A nonzero singular character matrix will be transformed to a matchcircuit composed of only Γ h -type gates. Γ i is used to realize zero matrix. To understand the composition of Γ c with other elementary gates, we need the following: Lemma 5.1. Suppose A is the character matrix of a k-bit matchcircuit ∆, and P 1 , P 2 are two arbitrary permutations on k elements. There exists matchcircuit Λ constructed from ∆ by adding some gates Γ c , such that the corresponding character matrices B satisfying

B 2 k -1,2 k -1 = A 2 k -1,2 k -1 and |B i 1 •••i k ,j 1 •••j k | = |A P 1 (i 1 •••i k ),P 2 (j 1 •••j k ) |.
The following lemma gives the transformation for matchcircuits. Lemma 5.2. For any k > 2, and any k-bit matchcircuit ∆ consisting of a single nonsingular k-bit matchgate Γ, there is a new matchcircuit Λ constructed by adding some invertible single and two-bit matchgates to ∆, such that the character matrix B of Λ is reducible. Furthermore, B is the character matrix of an even reducible matchgate.

So far we have established the result for the first significant case that a matchgate is applied to the first k bits.

In the following lemma we consider two more cases:

• a gate applied to consecutive bits but not starting from the first bit,

• a gate applied to nonconsecutive bits. For the first case, the gate must be an even or an odd gate, we observe that only even and odd gates are used in the transformation for an even or an odd gate. For the second case, we extend its matrix, and replace it by a new even gate which is applied to consecutive bits reducing it to the first case.

Lemma 5.3. For any k > 2, and any m-bit matchcircuit ∆ containing a k-bit matchgate Γ with character matrix A, there is a level k -1 matchcircuit Λ having the same character matrix as ∆.

The proof for lemma 5.1-5.3 will be given in the full version.

Proof of theorem 3.3

Proof. For (1). Repeat the process in lemma 5.3 until there is no gate of bit greater than 2.

For (2). The number of matchgates used in the phases of transformation are O(k), O(k 3 ), O(k) and O(k 2 ), respectively, so a k-bit matchgate can be simulated by O(k 4 ) many single and two-bit matchgates. This procedure is polynomial time computable, because there are polynomially many actions, and each action is polynomial time computable due to the fact that we compute only the edge entries.

Figure 1 :

 1 Figure 1: An example of matchcircuit.

Figure

  Figure 2: Exampleof k = 2. X 1 = {1, 2}, Y 1 = {6, 7}, T 1 = {4} X 2 = {8, 9}, Y 2 = {13, 14}, T 2 = {11}, W 1 = {1, 2, 3}, Z 1 = {5, 6, 7}, W 2 = {7, 8, 9}, Z 2 = {12, 13, 14}.

Figure 3 :

 3 Figure 3:

  (a), (b), (c), (d), (e), (f), (g), (h) and (i) respectively.

Figure 4 :

 4 Figure 4:

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Both authors are supported by the NSFC Grant no. 60325206 and no. 60310213. The second author is also supported by MATHLOGAPS (MEST-CT-2004-504029). c Angsheng Li and Mingji Xia

Action 1: First, we choose a nonzero edge entry. Since A [START_REF] Murota | Matrices and Matroids for Systems Analysis[END_REF] is nonsingular, there must be a nonzero edge entry A

(2) X ′ =X-{i},Y ′ =Y -{j} for some i and j. (Otherwise, all edge entries are zero's so that A [START_REF] Murota | Matrices and Matroids for Systems Analysis[END_REF] is a zero matrix, contradicting the non-singularity of A (0) .)

We use a gate of type Γ d , defined as follows: (i) connect each input-output pair other than the i-th or the j-th pair by an edge, (ii) the i-th input is connected to the j-th output, and (iii) the j-th input is connected to the i-th output. All edges are of weight 1. (See Fig. 3 (d)) Let C i,j denote the character matrix of the matchgate described above.

This action just turns A [START_REF] Murota | Matrices and Matroids for Systems Analysis[END_REF] to C i,k A [START_REF] Murota | Matrices and Matroids for Systems Analysis[END_REF] C j,k by connecting the matchgate of C i,k with the gate of A [START_REF] Murota | Matrices and Matroids for Systems Analysis[END_REF] , and the gate of C i,k in the order of left to right.

Firstly, we verify that action 1 realizes its goal. Generally, multiplying C a,b from left (resp. right) side is equivalent to exchanging pairs of rows (resp. columns)

Secondly, we analyze the cost of the action. Notice that the row exchanges are determined by a bit exchange on the labels of rows, so that the number of zeros in (the string of) the row label is kept unchanged. By definition, an edge entry can be exchanged only with another edge entry. Therefore all edge entries in the last row and column are kept zeros. In addition, it is easy to see that the left-bottom most entry is kept 1.

Action 2: We construct a matchgate with all of the input-output pairs connected by an edge of weight 1, except that the last pair is connected by an edge of weight w =

All entries of the character matrix of this matchgate are zeros, except for the diagonal entries. A diagonal entry (I, I) is w, if the last bit of I is 0, and 1, otherwise.

We multiply this character matrix with the current matrix, then a straightforward calculation shows that entry (2 k -1, 2 k -1) is turned to 1, while all the satisfied entries achieved previously are still preserved.

The goal of T3 is realized. Phase T4: This phase is similar to phase T2, except that we need consider the consequence on the last column and row. We start from changing the edge entries in column 2 k -2.

Phase T4 for column 2 k -2: Suppose we are going to change edge entry (X -{i}, Y -{nk + 1}) to zero by the order from bottom to top. Denote the action realizing this goal by action at (X -{i}, Y -{nk + 1}).

We construct the elementary matchgate used in the action at (X -{i}, Y -{nk + 1}). Each pair of input-output nodes of this matchgate is connected by an edge of weight 1, furthermore, the i-th input node is connected to the last output node by an edge of weight w, where w is either A X-{i},Y -{n-k+1} or -A X-{i},Y -{n-k+1} such that entry (X -{i}, Y -{nk + 1}) of the character matrix of the matchgate is -A X-{i},Y -{n-k+1} . (See Fig. 3 (e).)

We examine the nonzero entries in the character matrix L of the constructed matchgate. We first note that all diagonal entries are 1's. Let (I ′ , J ′ ) denote an arbitrary nonzero entry other than the diagonal entries of the matrix L. By construction of the matchgate, I ′ and J ′ differ at only the i-th and the k-th bits, and

{i} and I ′ , J ′ contain the same number of 0's, which is at least 1, where I ′ | i denotes the i-th bit of I ′ . The action at (X -{i}, Y -{nk + 1}) multiplies L with A from the left side. It makes some row transformations: for every such entry (I ′ , J ′ ) chosen as above, add row I ′ by the multiplication of row J ′ by L I ′ ,J ′ . So the goal of this action is realized.