text:
# The polytope of non-crossing graphs on a planar point set

## 1. Introduction and statement of results

### The polyhedron of non-crossing graphs

The set of (straight-line, or geometric) non-crossing graphs with a given set of vertices in the plane is of interest in Computational Geometry, Geometric Combinatorics, and related areas. In particular, much effort has been directed towards enumeration, counting and optimization on the set of maximal such graphs, that is to say, triangulations.

The poset structure of the set of non-crossing graphs, however, is only well understood if the points are in convex position. In this case the non-crossing graphs containing all the hull edges are the same as the polygonal subdivisions of the convex $`n`$-gon and, as is well-known, they form the face poset of the *$`(n3)`$-associahedron*.

In this paper we construct from $`𝒜`$ a polytope whose face poset contains the poset of non-crossing graphs on $`𝒜`$ embedded in a very nice way. In the following statement, and in the rest of the paper, we distinguish between vertices of $`\mathrm{conv}(𝒜)`$ (*extremal* points) and other points in the boundary of $`\mathrm{conv}(𝒜)`$, which we call *semi-interior* points.

###### Theorem 1.1.

Let $`𝒜`$ be a finite set of $`n`$ points in the plane, not all contained in a line. Let $`n_i`$, $`n_s`$ and $`n_v`$ be the number of interior, semi-interior and extremal points of $`𝒜`$, respectively.

There is a simple polytope $`Y_f(𝒜)`$ of dimension $`2n_i+n3`$, and a face $`F`$ of $`Y_f(𝒜)`$ (of dimension $`2n_i+n_v3`$) such that the complement of the star of $`F`$ in the face-poset of $`Y_f(𝒜)`$ equals the poset of non-crossing graphs on $`𝒜`$ that use all the convex hull edges.

This statement deserves some words of explanation:

* Our equality of posets reverses inclusions. Maximal non-crossing graphs (triangulations of $`𝒜`$) correspond to minimal faces (vertices of $`Y_f(𝒜)`$).
* We remind the reader that the *star* of a face $`F`$ in a polytope is the subposet of facets that contain $`F`$ and all their faces. In the complement of the star of $`F`$ we must consider the polytope $`Y_f(𝒜)`$ itself as an element, which corresponds to the graph with no interior edges.
* If $`𝒜`$ is in convex position, then $`Y_f(𝒜)`$ is the associahedron. The face $`F`$ is the whole polytope, whose star we must interpret as being empty.
* Our results are valid for point sets in non-general position. Our definition of non-crossing in this case is that if $`q`$ is between $`p`$ and $`r`$, then the edge $`pr`$ cannot appear in a non-crossing graph, regardless of whether $`q`$ is incident to an edge in the graph. This definition has the slight drawback that a graph which is non-crossing in a point set $`𝒜`$ may become crossing in $`𝒜\{p\}`$, but it makes maximal crossing-free graphs coincide with the triangulations of $`𝒜`$ (with the convention, standard in Computational Geometry, that triangulations of $`𝒜`$ are required to use all the points of $`𝒜`$ as vertices). To be consistent with this, a convex hull edge is an edge between two consecutive extremal or semi-interior points of $`𝒜`$ in the boundary of $`\mathrm{conv}(𝒜)`$.
* Since convex hull edges are irrelevant to crossingness, the poset of all non-crossing graphs on $`𝒜`$ is the direct product of the poset in the statement and a Boolean poset of rank $`n_v+n_s`$.

We give a fully explicit facet description of $`Y_f(𝒜)`$. It lives in $`^{3n}`$ and is defined by the 3 linear equalities (1) and the $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)+n`$ linear inequalities (4) and (5) of Section 3, with some of them turned into equalities. (With one exception: for technical reasons, if $`𝒜`$ contains three collinear boundary points we need to add extra points to its exterior and obtain $`Y_f(𝒜)`$ as a face of the polytope $`Y_f(𝒜^{})`$ of the extended point set $`𝒜^{}`$).

The $`f_{ij}`$’s in equations (4) and (5) and in the notation $`Y_f(𝒜)`$ denote a vector in $`^{\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)}`$. Our construction starts with a linear cone $`\overline{Y_0}(𝒜)`$ (Definition 3.1) whose facets are then translated using the entries of $`f`$ to produce a polyhedron $`\overline{Y_f}(𝒜)`$, of which the polytope $`Y_f(𝒜)`$ is the unique maximal bounded face. Our proof goes by analyzing the necessary and sufficient conditions for $`f`$ to produce a polytope with the desired properties and then proving the existence of valid choices of $`f`$. In particular, Theorem 3.7 shows one valid choice. This is essentially the same approach used in  for the polytope of pointed non-crossing graphs constructed there, which is actually the face $`F`$ of $`Y_f(𝒜)`$ referred too in the statement. Our results generalize the construction in  in two directions: on the one hand they refer to all non-crossing graphs (not only pointed ones) and on the other hand we show how to deal with non-general position.

Mapping the instances of a combinatorial object to the vertices of a certain polytope is useful for optimization and enumeration purposes. In the case of triangulations, two such polytopes have been used in the past; the “secondary polytope”  and the “universal polytope”  of the point set. Our construction adds to these two, but it has one advantage: We have an explicit facet description of the polytope. In the secondary polytope, facets correspond to the coarse polygonal subdivisions of $`𝒜`$, which have no easy characterization. In the universal polytope, the facet description in  gives only a linear programming relaxation of the polytope, which makes integer programming be needed in order to optimize linear functionals on it.

That the poset we are interested in is not the whole poset of faces of the polytope $`Y_f(𝒜)`$ may seem a serious drawback for using it as a tool for enumeration of all the triangulations of a planar point set. But the subposet we are interested in is not just a subposet. Being the complement of the star of a face $`F`$ has theoretical and practical implications. On the one hand, it implies that the poset is a shellable ball of dimension $`2n_i+n4`$, since there is a shelling order ending in the facets that contain $`F`$. On the other hand, the part of the boundary of $`Y_f(𝒜)`$ that we are interested in becomes the (strict) lower envelope of a convex polyhedron via any projective transformation that sends a supporting hyperplane of $`F`$ to the infinity.

### The polytope of pseudo-triangulations

Actually, the set of all the vertices of the polytope $`Y_f(𝒜)`$ is interesting on its own merits:

###### Theorem 1.2.

The vertex set of the polytope $`Y_f(𝒜)`$ of Theorem 1.1 is in bijection to the set of all pseudo-triangulations of $`𝒜`$. The 1-skeleton of $`Y_f(𝒜)`$ is the graph of flips between them.

A pseudo-triangle is a perhaps non-convex polygon with three corners (non-reflex vertices). A pseudo-triangulation of $`𝒜`$ is a subdivision of $`\mathrm{conv}(𝒜)`$ into pseudo-triangles using $`𝒜`$ as vertex set. As an example, Figure 1 shows the pseudo-triangulations of a set of four extremal points and one interior point, with the graph of flips between them embedded as (a Schlëgel diagram of) a 4-dimensional polytope. The face $`F`$ of Theorem 1.1 is actually the facet on which the Schlëgel diagram has been performed. Why the interior point is “unmarked” in the three triangulations of the point set and “marked” in the other 8 pseudo-triangulations will be explained in Section 2.

Pseudo-triangulations, first introduced by Pocchiola and Vegter around 1995 (see ), have by now been used in many Computational Geometry applications, among them visibility , ray shooting , and kinetic data structures . Streinu  introduced the *minimum* or *pointed pseudo-triangulations* (p.p.t.’s, for short), proved certain surprising relations of them to structural rigidity of non-crossing graphs, and used them to prove the Carpenter’s Rule Theorem (the first proof of which was given shortly before by Connelly et al ). P.p.t.’s can also be described as the maximal non-crossing and pointed graphs. See all the relevant definitions in Section 2.

The paper , using these rigid theoretic properties of p.p.t.’s, constructed a polytope $`X_f(𝒜)`$ whose vertex set is precisely the set of p.p.t.’s of a given point set. Our construction is heavily based on it (but this paper is mostly self-contained). Our method not only extends that construction to cover all pseudo-triangulations, it also shows that the method can easily be adapted to point sets in non-general position, with a suitable definition of pseudo-triangulation for such point sets (Definition 5.1).

The flips between pseudo-triangulations that appear in our Theorem 1.2 are introduced in Section 2 (see Definition 2.5) for point sets in general position and in Section 5 (see Definition 5.5 and Figures 10 and 11) for point sets with collinearities. The definition is new (to the best of our knowledge) but in the case of general position it has independently been considered in , where flips between pseudo-triangulations are related to geometric flips between polyhedral terrains. It is proved there that the graph of flips of a point set $`𝒜`$ (that is, the 1-skeleton of our polytope) has diameter bounded by $`O(n\mathrm{log}(n))`$. The same bound for the graph of pointed pseudo-triangulations (the 1-skeleton of the face $`F`$) has been obtained in .

Our flips restrict to the ones in  and  when the two pseudo-triangulations involved are pointed, and they are also related to the flips of Pocchiola and Vegter  as follows: Pocchiola and Vegter were interested in pseudo-triangulations of a set $`𝒪:=\{o_1,\mathrm{},o_n\}`$ of convex bodies, and they defined a graph of flips between them. That graph is regular of degree $`3n3`$. Pocchiola (personal communication) has shown that taking each $`o_i`$ to be a sufficiently small convex body around each point, our graph is obtained from the one in  by contraction of certain edges.

### Constrained pseudo-triangulations

It is sometimes convenient to study pseudo-triangulations or non-crossing graphs on $`𝒜`$ that contain a specified subset of edges. For example, the pseudo-triangulations of a non-convex polygon $`P`$, are in bijection with pseudo-triangulations of the point set $`𝒜=\mathrm{vertices}(P)`$ which use all the boundary edges of $`P`$ and any (arbitrarily chosen) triangulation of $`\mathrm{conv}(P)\backslash P`$. We can even allow for additional interior points of $`P`$ to be used as vertices (a situation called an “augmented polygon” in ).

We want to emphasize that our results apply to these and other cases: since each facet of $`Y_f(𝒜)`$ corresponds to the presence of a certain edge, pseudo-triangulations or non-crossing graphs that contain a specific non-crossing graph $`G`$ correspond to faces or vertices of $`Y_f(𝒜)`$ contained in the face that corresponds to $`G`$.

###### Corollary 1.3.

Let $`G`$ be a non-crossing graph on $`𝒜`$ with $`k`$ non-boundary edges (edges not in the boundary of $`\mathrm{conv}(𝒜)`$). Then, the set of pseudo-triangulations of $`𝒜`$ that contain $`G`$ as a subgraph is the vertex set of a simple polytope of dimension $`2n_i+n3k`$, whose 1-skeleton is the graph of flips between them.

In particular, the pseudo-triangulations of a non-convex polygon $`P`$ with $`n`$ vertices are the vertex set of a polytope of dimension $`n3`$.

Figure 2 shows the (3-dimensional) polytope of pseudo-triangulations of a certain non-convex hexagon.

### Pseudo-triangulations are rigid

Our construction has also rigid-theoretic consequences. A generically rigid graph (for dimension 2) is a graph which becomes rigid in almost all its straight-line embeddings in the plane. Generically rigid graphs need at least $`2n3`$ edges, because that is the number of degrees of freedom of $`n`$ points in the plane (after neglecting rigid motions). Generically rigid graphs with exactly $`2n3`$ edges are called *isostatic* and they admit the following characterization, due to Laman (see, for example, ): they are the graphs with $`2n3`$ edges and with the property that any subset of $`kn2`$ vertices is incident to at least $`2k`$ edges. Using this characterization, Ileana Streinu  proved that every pointed pseudo-triangulations is an isostatic graph. We have the following generalization:

###### Theorem 1.4.

Let $`T`$ be a pseudo-triangulation of a planar point set $`𝒜`$ in general position. Let $`G`$ be its underlying graph. Then:

1. $`G`$ is infinitesimally rigid, hence rigid and generically rigid.
2. There are at least $`2k+3l`$ edges of $`T`$ incident to any subset of $`k`$ pointed plus $`l`$ non-pointed vertices of $`T`$ (assuming $`k+ln2`$).

In the statement, “general position” can actually be weakened to “no three boundary points of $`𝒜`$ are collinear. In the presence of boundary collinearities, non-rigid pseudo-triangulations (for our definition) exist. For example, only six of the fourteen pseudo-triangulations of the point set of Figure 11 are rigid.

If we recall that a pseudo-triangulation with $`k`$ non-pointed vertices has exactly $`2n3+k`$ edges (see Proposition 2.2), Theorem 1.4 has the consequence that the space of self-stresses on a pseudo-triangulation has exactly dimension $`k`$. This fact follows also from the results of .

### Two open questions

* Can every planar and generically rigid graph be embedded as a pseudo-triangulation? That the answer is positive should be considered a conjecture of the set of authors of , a paper that actually solves the minimal case: planar Laman graphs can be embedded as pointed pseudo-triangulations. The maximal case (combinatorial triangulations can be drawn with convex faces) is also solved, by Tutte’s theorem . But the intermediate cases remain open.
* Are non-crossing graphs on $`𝒜`$ the face poset of a polyhedron? A naive answer would be that such a polyhedron is obtained by just deleting from the facet definition of $`Y_f(𝒜)`$ those facets containing $`F`$. But this does not work even in the point set with a single point in general position in the interior of a quadrilateral (the one in Figure 1). Using the equations that define the polytope it can be checked that the removal of the facet $`F`$ in this example gives a polyhedron with two extra vertices, not present in $`Y_f(𝒜)`$.

## 2. The graph of all pseudo-triangulations of $`𝒜`$

All throughout this section, $`𝒜`$ denotes a set of $`n`$ points in general position in the plane, $`n_i`$ of them in the interior of $`\mathrm{conv}(𝒜)`$ and $`n_v`$ in the boundary. Point sets in non-general position are studied in Section 5.

###### Definition 2.1.

A *pseudo-triangle* is a simple polygon with only three convex vertices (called *corners*) joined by three inward convex polygonal chains (called *pseudo-edges* of the pseudo-triangle).

A *pseudo-triangulation of $`𝒜`$* is a geometric non-crossing graph with vertex set $`𝒜`$ and which partitions $`\mathrm{conv}(𝒜)`$ into pseudo-triangles.

Part (a) of Figure 3 shows a pseudo-triangle. Parts (b) and (c) show two pseudo-triangulations.

Since the maximal non-crossing graphs on $`𝒜`$ (the *triangulations* of $`𝒜`$) are a particular case of pseudo-triangulations, they are the maximal pseudo-triangulations. As is well-known, they all have $`2n_v+3n_i3`$ edges. It turns out that the pseudo-triangulations with the minimum possible number of edges are also very interesting from different points of view. We recall that a vertex of a geometric graph is called *pointed* if all its incident edges span an angle smaller than 180 degrees from that vertex. The graph itself is called pointed if all its vertices are pointed. The following statement comes originally from  and a proof can also be found in .

###### Proposition 2.2 (Streinu).

Let $`𝒜`$ be a planar point set as above. Then:

1. Every pseudo-triangulation of $`𝒜`$ with $`n_\gamma `$ non-pointed vertices and $`n_ϵ`$ pointed vertices has: $`2n3+n_\gamma =3n3n_ϵ`$ edges.
2. Every pointed and planar graph on $`𝒜`$ has at most $`2n3`$ edges, and is contained in some pointed pseudo-triangulation of $`𝒜`$.

Part 1 implies that, among pseudo-triangulations of $`𝒜`$, pointed ones have the minimum possible number of edges . For this reason they are sometimes called *minimum pseudo-triangulations*. Part 2 says that pointed pseudo-triangulations coincide with maximal non-crossing and pointed graphs.

Another crucial property of pseudo-triangulations is the existence of a natural notion of flip. Let $`e`$ be an interior edge in a pseudo-triangulation $`T`$ of $`𝒜`$ and let $`\sigma `$ be the union of the two pseudo-triangles incident to $`e`$. We regard $`\sigma `$ as a graph, one of whose edges is $`e`$. We can consider $`\sigma e`$ to be a (perhaps degenerate) polygon, with a well-defined boundary cycle; in degenerate cases some edges and vertices may appear twice in the cycle. See an example of what we mean in Figure 4, in which the cycle of vertices is $`pqrstsu`$ and the cycle of edges is $`pq,qr,rs,st,ts,su,up`$. As in any polygon, each (appearance of a) vertex in the boundary cycle of $`\sigma e`$ is either concave or convex. In the figure, there are four convex vertices (corners), namely $`r`$, second appearance of $`s`$, $`u`$ and $`q`$. Then:

###### Lemma 2.3.

* $`\sigma e`$ has either 3 or 4 corners.
* It has 3 corners if and only if exactly one of the two end-points of $`e`$ is pointed in $`\sigma `$. In this case $`Te`$ is still a pseudo-triangulation.
* It has 4 corners if and only if both end-points of $`e`$ are pointed in $`\sigma `$. In this case $`Te`$ is not a pseudo-triangulation and there is a unique way to insert an edge in $`Te`$ to obtain another pseudo-triangulation.

###### Proof.

Let $`v_1`$ and $`v_2`$ be the two end-points of $`e`$. For each $`v_i`$, one of the following three things occur: (a) $`v_i`$ is not-pointed in $`\sigma `$, in which case it is a corner of the two pseudo-triangles incident to $`e`$ and is not a corner of $`\sigma e`$; (b) $`v_i`$ is pointed in $`\sigma `$ with the big angle exterior to $`\sigma `$, in which case it is a corner of both pseudo-triangles and of $`\sigma e`$ as well, or (c) $`v_i`$ is pointed with its big angle interior, in which case it is a corner in only one of the two pseudo-triangles and not a corner in $`\sigma e`$.

In case (a), $`v_i`$ contributes two more corners to the two pseudo-triangles than to $`\sigma e`$. In the other two cases, it contributes one more corner to the pseudo-triangles than to $`\sigma e`$. Since the two pseudo-triangles have six corners in total, $`\sigma e`$ has four, three or two corners depending on whether both, one or none of $`v_1`$ and $`v_2`$ are pointed in $`\sigma `$. The case of two corners is clearly impossible, which finishes the proof of 1. Part 2 only says that “degenerate pseudo-triangles” cannot appear.

Part 3 is equivalent to saying that a pseudo-quadrangle (even a degenerate one) can be divided into two pseudo-triangles in exactly two ways. Indeed, these two partitions are obtained drawing the geodesic arcs between two opposite corners. Such a geodesic path consists of a unique interior edge and (perhaps) some boundary edges. ∎

Cases (2) and (3) of the above lemma will define two different types of flips in a pseudo-triangulation. The inverse of the first one is the insertion of an edge, in case this keeps a pseudo-triangulation. The following statement states exactly when this happens:

###### Lemma 2.4.

Let $`T`$ be a pseudo-triangle with $`k`$ non-corners. Then, every interior edge dividing $`T`$ into two pseudo-triangles makes non-pointed exactly one non-corner. Moreover, there are exactly $`k`$ such interior edges, each making non-pointed a different non-corner.

###### Proof.

The first sentence follows from Lemma 2.3, which says that exactly one of the two end-points of the edge inserted is pointed (after the insertion). For each non-corner, pointedness at the other end of the edge implies that the edge is the one that arises in the geodesic arc that joins that non-corner to the opposite corner. This proves uniqueness and existence. ∎

###### Definition 2.5.

(Flips in pseudo-triangulations)  Let $`T`$ be a pseudo-triangulation. We call *flips* in $`T`$ the following three types of operations, all producing pseudo-triangulations. See examples in Figure 5:

* (*Deletion flip*). The removal of an edge $`eT`$, if $`Te`$ is a pseudo-triangulation.
* (*Insertion flip*). The insertion of an edge $`eT`$, if $`Te`$ is a pseudo-triangulation.
* (*Diagonal flip*). The exchange of an edge $`eT`$, if $`Te`$ is not a pseudo-triangulation, for the unique edge $`e^{}`$ such that $`(Te)e^{}`$ is a pseudo-triangulation.

The *graph of pseudo-triangulations* of $`𝒜`$ has as vertices all the pseudo-triangulations of $`𝒜`$ and as edges all flips of any of the types.

###### Proposition 2.6.

The graph of pseudo-triangulations of $`𝒜`$ is connected and regular of degree $`3n_i+n_v3=3n2n_v3`$.

###### Proof.

There is one diagonal or deletion flip for each interior edge, giving a total of $`3n3n_ϵn_v`$ by Proposition 2.2. There are as many insertion flips as pointed interior vertices by Lemma 2.4, giving $`n_ϵn_v`$.

To establish connectivity, let $`p`$ be a point on the convex hull of $`𝒜`$. The pseudo-triangulations of $`𝒜`$ with degree 2 at $`p`$ coincide with the pseudo-triangulations of $`𝒜\{p\}`$ (together with the two tangents from $`p`$ to $`𝒜\{p\}`$). By induction, we assume all those pseudo-triangulations to be connected in the graph. On the other hand, in pseudo-triangulations with degree greater than 2 at $`p`$ all interior edges incident to $`e`$ can be flipped and produce pseudo-triangulations with smaller degree at $`e`$. (Remark: if $`p`$ is an interior point, then a diagonal-flip on an edge incident to $`p`$ may create another edge incident to $`p`$; but for a boundary point this cannot be the case since $`p`$ is a corner in the pseudo-quadrilateral $`\sigma e`$ of Lemma 2.3). Decreasing one by one the number of edges incident to $`p`$ will eventually lead to a pseudo-triangulation with degree 2 at $`p`$. ∎

###### Remarks 2.7.

It is an immediate consequence of Lemma 2.3 that every interior edge in a pointed pseudo-triangulation is flippable. This shows that the graph of diagonal-flips between pointed pseudo-triangulations of $`𝒜`$ is regular of degree $`2n_i+n_v3`$, a crucial fact in .

As another remark, one may be tempted to think that two pseudo-triangulations are connected by a diagonal flip if and only if one is obtained from the other by the removal and insertion of a single edge, but this is not the case: The two pseudo-triangulations of Figure 6 are not connected by a diagonal flip, according to our definition, because the intermediate graph $`Te`$ is a pseudo-triangulation.

### Marked non-crossing graphs on $`𝒜`$.

As happened with pointed pseudo-triangulations, Proposition 2.6 suggests that the graph of pseudo-triangulations of $`𝒜`$ may be the skeleton of a simple polytope of dimension $`3n_i+n_v3`$. As a step towards this result we first look at what the face poset of such a polytope should be. The polytope being simple means that we want to regard each pseudo-triangulation $`T`$ as the upper bound element in a Boolean poset of order $`3n32n_v`$. This number equals, by Proposition 2.2, the number of interior edges plus interior pointed vertices in $`T`$:

###### Definition 2.8.

A *marked graph* on $`𝒜`$ is a geometric graph with vertex set $`𝒜`$ together with a subset of its vertices, that we call “marked”. We call a marked graph non-crossing if it is non-crossing as a graph and marks arise only in pointed vertices.

We call a non-crossing marked graph *fully-marked* if it is marked at all pointed vertices. If, in addition, it is a pseudo-triangulation, then we call it a *fully-marked pseudo-triangulation*, abbreviated as *f.m.p.t.*

Marked graphs form a poset by inclusion of both the sets of edges and of marked vertices. We say that a marked graph contains the boundary of $`𝒜`$ if it contains all the convex hull edges and convex hull marks. The following results follow easily from the corresponding statements for non-crossing graphs and pseudo-triangulations.

###### Proposition 2.9.

With the previous definitions:

1. Every marked pseudo-triangulation of $`𝒜`$ with $`n_\gamma `$ non-pointed vertices, $`n_ϵ`$ pointed vertices and $`n_m`$ marked vertices, has $`2n3+n_\gamma +n_m=3n3n_ϵ+n_m`$ edges plus marks. In particular, all fully-marked pseudo-triangulations have $`3n3`$ edges plus marks, $`3n32n_v`$ of them interior.
2. Fully-marked pseudo-triangulations of $`𝒜`$ and maximal non-crossing marked graphs on $`𝒜`$ are the same thing.
3. (Flips in marked pseudo-triangulations) In a fully-marked pseudo-triangulation of $`𝒜`$, every interior edge or interior mark can be *flipped*; once removed, there is a unique way to insert another edge or mark to obtain a different fully-marked pseudo-triangulation of $`𝒜`$. The graph of flips between fully-marked pseudo-triangulations of $`𝒜`$ equals the graph of pseudo-triangulations of $`𝒜`$ of Definition 2.5. ∎

These properties imply that, if the graph of pseudo-triangulations of $`𝒜`$ is to be the skeleton of a simple polytope, then the face poset of that polytope must be (opposite to) the inclusion poset of *non-crossing marked graphs containing the boundary of $`𝒜`$*. Indeed, this poset has the right “1-skeleton” and the right lower ideal below every fully-marked pseudo-triangulation (a Boolean lattice of order $`3n32n_v`$).

## 3. The polyhedron of marked non-crossing graphs on $`𝒜`$

In the first part of this section we do not assume $`𝒜`$ to be in general position. Only after Definition 3.6 we need general position, among other things because we have not yet defined marked non-crossing graphs or pseudo-triangulations for point sets in special position. That will be done in Section 5.

The setting for our construction is close to the rigid-theoretic one used in . There, the polytope to be constructed is embedded in the space $`^{2n3}`$ of all infinitesimal motions of the $`n`$ points $`p_1,\mathrm{},p_n`$. The space has dimension $`2n3`$ because the infinitesimal motion of each point produces two coordinates (an infinitesimal velocity $`v_i^2`$) but global translations and rotations produce a 3-dimensional subspace of trivial motions which are neglected. Formally, this can be done by a quotient $`^{2n}/M_0`$, where $`M_0`$ is the 3-dimensional subspace of trivial motions, or it can be done by fixing three of the $`2n`$ coordinates to be zero. For example, if the points $`p_1`$ and $`p_2`$ do not lie in the same horizontal line, one can take

$$v_1^1=v_1^2=v_2^1=0.$$

In our approach, we will consider a third coordinate $`t_i`$ for each point, related to the “marks” discussed in the previous paragraphs, or to pointedness of the vertices.

That is to say, given a set of $`n`$ points $`𝒜=\{p_1,\mathrm{},p_n\}`$ in $`^2`$, we consider the following $`(3n3)`$-dimensional space;

$$\begin{array}{c}S:=\{(v_1,\mathrm{},v_n,t_1,\mathrm{},t_n)\left(^2\right)^n\times ^n:v_1^1=v_1^2=v_2^1=0\}^{3n}.\end{array}$$
(1)
In it we consider the following $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)+n`$ linear inequalities

$$H_{ij}^+:=\{(v,t)S:p_ip_j,v_iv_j|p_ip_j|(t_i+t_j)0\}$$
(2)
and

$$H_{0j}^+:=\{(v,t)S:t_j0\}.$$
(3)
We denote by $`H_{i,j}`$ and $`H_{0,j}`$ their boundary hyperplanes.

###### Definition 3.1.

We call *expansion cone* of $`𝒜`$ and denote it $`\overline{Y_0}(𝒜)`$ the positive region of the above hyperplane arrangement:

$$\overline{Y_0}(𝒜):=\underset{i,j\{0,1,\mathrm{},n\}}{}H_{ij}^+$$

When clear from the context we will omit the point set $`𝒜`$ and use just $`\overline{Y_0}`$.

Observe that the equations defining $`\overline{Y_0}`$ imply that for every $`i,j`$:

$$p_ip_j,v_iv_j|p_ip_j|(t_i+t_j)0.$$

In particular, the vector $`(v_1,\mathrm{},v_n)`$ is an expansive infinitesimal motion of the point set, in the standard sense.

###### Lemma 3.2.

The polyhedron $`\overline{Y_0}(𝒜)`$ has full dimension $`3n3`$ in $`S^{3n}`$ and it is a pointed polyhedral cone. (Here, “pointed” means “having the origin as a vertex” or, equivalently, “containing no opposite non-zero vectors”).

###### Proof.

The vector $`(v,t)`$ with $`v_i:=p_i,t_i:=\mathrm{min}_{k,l}\{|p_kp_l|\}/4`$ satisfies all the inequalities (2) and (3) strictly. In order to obtain a point in $`S`$ we add to it a suitable infinitesimal trivial motion.

To prove that the cone is pointed, suppose that it contains two opposite vectors $`(v,t)`$ and $`(v,t)`$. Equivalently, that $`(v,t)`$ lies in all the hyperplanes $`H_{i,j}`$ and $`H_{0,i}`$. That is to say, $`t_i=0`$ for every $`i`$ and

$$v_jv_i,p_jp_i=0$$

for all $`i,j`$. These last equations say that $`(v_1,\mathrm{},v_n)`$ is an infinitesimal flex of the complete graph on $`𝒜`$. Since the complete graph on every full-dimensional point set is infinitesimally rigid, $`(v_1,\mathrm{},v_n)`$ is a trivial motion and equations (1) imply that the motion is zero. ∎

An edge $`p_ip_j`$ or a point $`p_i`$ are called tight for a certain vector $`(v,t)\overline{Y_0}`$ if $`(v,t)`$ lies in the corresponding hyperplane $`H_{i,j}`$ or $`H_{0,i}`$. We call supporting graph of any $`(v,t)`$ and denote it $`T(v,t)`$ the marked graph of tight edges for $`(v,t)`$ with marks at tight points for $`(v,t)`$.

###### Lemma 3.3.

Let $`(v,t)\overline{Y_0}`$. If $`T(v,t)`$ contains the boundary edges and vertices of a convex polygon, then $`v_l=0`$ and $`t_l=0`$ for every point $`p_l`$ in the interior of the polygon. Therefore, $`T(v,t)`$ contains the complete marked graph on the set of vertices and interior points of the polygon.

Observe that this statement says nothing about points in the relative interior of a boundary edge, if the polygon has collinear points in its boundary. Indeed, such points may have a non-zero $`v_l`$, namely the exterior normal to the boundary edge containing the point.

###### Proof.

The hypotheses are equivalent to $`t_i=0`$ and $`p_ip_j,v_iv_j=0`$ for all the boundary vertices $`p_i`$ and boundary edges $`p_ip_j`$ of the convex polygon. We first claim that the infinitesimal expansive motion $`v=(v_1,\mathrm{},v_n)`$ also preserves distances between non-consecutive polygon vertices. Since the sum of interior angles at vertices of an $`n`$-gon is independent of coordinates, a non-trivial motion fixing the lengths of boundary edges would decrease the interior angle at some polygon vertex $`p_i`$ and then its adjacent boundary vertices get closer, what contradicts (2). Hence, $`v`$ is a translation or rotation of the polygon boundary which, by equations (1), is zero. On the other hand, if $`v_k0`$ for any $`p_k`$ interior to the polygon, then $`p_k`$ gets closer to some boundary vertex, what using $`t_k0`$ contradicts (2) again.

Therefore, $`v_l=0`$ for every point $`p_l`$ enclosed in the polygon (what can be concluded from \[15, Lemma 3.2(b)\] as well). Then, the equation (2) corresponding to $`p_l`$ and to any point $`p_i`$ in the boundary of the polygon implies that $`t_l0`$. Together with the equation (3) corresponding to $`p_l`$ this implies $`t_l=0`$. ∎

Obviously, $`\overline{Y_0}`$ is not the polyhedron we are looking for, since its face poset does not have the desired combinatorial structure; it has a unique vertex while $`𝒜`$ may have more than only one fully-marked pseudo-triangulation. The right polyhedron for our purposes is going to be a convenient perturbation of $`\overline{Y_0}`$ obtained by translation of its facets.

###### Definition 3.4.

For each $`f^{\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)}`$ (with entries indexed $`f_{i,j}`$, for $`i,j\{0,\mathrm{},n\}`$) we call polyhedron of expansions constrained by $`f`$, and denote it $`\overline{Y_f}(𝒜)`$, the polyhedron defined by the $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ equations

$$p_ip_j,v_iv_j|p_ip_j|(t_i+t_j)f_{ij}$$
(4)
for every $`p_i,p_j𝒜`$ and the $`n`$ equations

$$t_jf_{0j},p_i𝒜.$$
(5)
From Lemma 3.2, we conclude that:

###### Corollary 3.5.

$`\overline{Y_f}(𝒜)`$ is a $`(3n3)`$-dimensional unbounded polyhedron with at least one vertex, for any $`f`$. ∎

In the rest of this section and in Section 4 we assume $`𝒜`$ to be in general position. As before, to each feasible point $`(v,t)\overline{Y_f}`$ we associate the marked graph consisting of edges and vertices whose equations (4) and (5) are tight on $`(v,t)`$. Similarly, to a face $`F`$ of $`\overline{Y_f}`$ we associate the tight marked graph of any of its relative interior points. This gives an (order-reversing) embedding of the face poset of $`\overline{Y_f}`$ into the poset of all marked graphs of $`𝒜`$. Our goal is to show that for certain choices of the constraint parameters $`f`$, the face poset of $`\overline{Y_f}`$ coincides with that of non-crossing marked graphs on $`𝒜`$.

###### Definition 3.6.

We define a choice of the constants $`f`$ to be *valid* if the tight marked graph $`T(F)`$ of every face $`F`$ of $`\overline{Y_f}`$ is non-crossing.

The proof that valid choices exist for any point set is postponed to Section 4, in order not to interrupt the current flow of ideas. In particular, Corollary 4.5 implies that the following explicit choice is valid:

###### Theorem 3.7.

The choice $`f_{ij}:=det(O,p_i,p_j)^2`$, $`f_{0j}:=0`$ is valid.

The main statement in the paper is then:

###### Theorem 3.8.

(The polyhedron of marked non-crossing graphs) If $`f`$ is a valid choice of parameters, then $`\overline{Y_f}`$ is a simple polyhedron of dimension $`3n3`$ whose face poset equals (the opposite of) the poset of non-crossing marked graphs on $`𝒜`$. In particular:

1. Vertices of the polyhedron are in 1-to-1 correspondence with fully-marked pseudo-triangulations of $`𝒜`$.
2. Bounded edges correspond to flips of interior edges or marks in fully-marked pseudo-triangulations, i.e., to fully-marked pseudo-triangulations with one interior edge or mark removed.
3. Extreme rays correspond to fully-marked pseudo-triangulations with one convex hull edge or mark removed.

###### Proof.

By Corollary 3.5, every vertex $`(v,t)`$ of $`\overline{Y_f}`$ has at least $`3n3`$ incident facets. By Proposition 2.9, if $`f`$ is valid then the marked graph of any vertex of $`\overline{Y_f}`$ has exactly $`3n3`$ edges plus marks and is a fully-marked pseudo-triangulation. This also implies that the polyhedron is simple. If we prove that all the fully-marked pseudo-triangulations appear as vertices of $`\overline{Y_f}`$ we finish the proof, because then the face poset of $`\overline{Y_f}`$ will have the right minimal elements and the right upper ideals of minimal elements (the Boolean lattices of subgraphs of fully-marked pseudo-triangulations) to coincide with the poset of non-crossing marked graphs on $`𝒜`$.

That all fully-marked pseudo-triangulations appear follows from connectedness of the graph of flips: Starting with any given vertex of $`\overline{Y_f}`$, corresponding to a certain f.m.p.t. $`T`$ of $`𝒜`$, its $`3n3`$ incident edges correspond to the removal of a single edge or mark in $`T`$. Moreover, if the edge or mark is not in the boundary, Lemma 3.3 implies that the edge (of $`\overline{Y_f}`$) corresponding to it is bounded because it collapses to the origin in $`\overline{Y_0}`$. Then, this edge connects the original vertex of $`\overline{Y_f}`$ to another one which can only be the f.m.p.t. given by the flip in the corresponding edge or mark of $`T`$. Since this happens for all vertices, and since all f.m.p.t.’s are reachable from any other one by flips, we conclude that they all appear as vertices. ∎

From Theorems 3.7 and 3.8 it is easy to conclude the statements in the introduction. The following is actually a more precise statement implying both:

###### Theorem 3.9.

(The polytope of all pseudo-triangulations) Let $`Y_f(𝒜)`$ be the face of $`\overline{Y_f}(𝒜)`$ defined turning into equalities the equations (4) and (5) which correspond to convex hull edges or convex hull points of $`𝒜`$, and assume $`f`$ to be a valid choice. Then:

1. $`Y_f(𝒜)`$ is a simple polytope of dimension $`2n_i+n3`$ whose 1-skeleton is the graph of pseudo-triangulations of $`𝒜`$. (In particular, it is the unique maximal bounded face of $`\overline{Y_f}(𝒜)`$).
2. Let $`F`$ be the face of $`Y_f(𝒜)`$ defined by turning into equalities the remaining equations (5). Then, the complement of the star of $`F`$ in the face-poset of $`Y_f(𝒜)`$ equals the poset of non-crossing graphs on $`𝒜`$ that use all the convex hull edges.

###### Proof.

(1) That $`Y_f(𝒜)`$ is a bounded face follows from Lemma 3.3 (it collapses to the zero face in $`\overline{Y_0}(𝒜)`$). Since vertices of $`\overline{Y_f}(𝒜)`$ are f.m.p.t.’s and since all f.m.p.t.’s contain all the boundary edges and vertices, $`Y_f(𝒜)`$ contains all the vertices of $`\overline{Y_f}(𝒜)`$. Hence, its vertices are in bijection with all f.m.p.t.’s which, in turn, are in bijection with pseudo-triangulations. Edges of $`Y_f(𝒜)`$ correspond to f.m.p.t.’s minus one interior edge or mark, which are precisely the flips between f.m.p.t.’s, or between pseudo-triangulations.

(2) The facets containing $`F`$ are those corresponding to marks in interior points. Then, the faces in the complement of the star of $`F`$ are those in which none of the inequalities (5) are tight; that is to say, they form the poset of “non-crossing marked graphs containing the boundary edges and marks but no interior marks”, which is the same as the poset of non-crossing graphs containing the boundary. ∎

We now turn our attention to Theorem 1.4. Its proof is based in the use of the homogeneous cone $`\overline{Y_0}(𝒜)`$ or, more preciesely, the set $`:=\{H_{ij}:i,j=1,\mathrm{},n\}\{H_{0i}:i=1,\mathrm{},n\}`$ of hyperplanes that define it.

###### Proof of Theorem 1.4.

Observe now that the equations defining $`H_{ij}`$, specialized to $`t_i=0`$ for every $`i`$, become the equations of the infinitesimal rigidity of the complete graph on $`𝒜`$. In particular, a graph $`G`$ is rigid on $`𝒜`$ if and only if the intersection

$$\left(_{ijG}H_{ij}\right)\left(_{i=1}^nH_{0i}\right)$$

equals 0.

This happens for any pseudo-triangulation because Theorem 3.8 implies that the hyperplanes corresponding to the $`3n3`$ edges and marks of any fully-marked pseudo-triangulation form a basis of the (dual of) the linear space $`S`$.

To prove part (2) we only need the fact that the $`3n3`$ linear hyperplanes corresponding to a fully-marked pseudo-triangulation are independent. In particular, any subset of them is independent too. We consider the subset corresponding to the induced (marked) subgraph on the $`nkl`$ vertices other than the $`k`$ pointed and $`l`$ non-pointed ones we are interested in. They form an independent set involving only $`3(nkl)`$ coordinates, hence their number is at most $`3(nkl)3`$ (we need to subtract 3 for the rigid motions of the $`nkl`$ points, and here is where we need $`k+ln2`$). Since the fully-marked pseudo-triangulation has $`3n3`$ edges plus marks, at least $`3k+3l`$ of them are incident to our subset of points. And exactly $`k`$ marks are incident to our points, hence at least $`2k+3l`$ edges are. ∎

Actually, we can derive some consequences for general planar rigid graphs. Observe that every planar and generically rigid graph $`G`$ must have between $`2n3`$ and $`3n3`$ edges (the extreme cases being an isostatic graph and a triangulation of the $`2`$-sphere). Hence, we can say that the graph $`G`$ has $`2n3+y`$ edges, where and $`0yn3`$. If the graph can be embedded as a pseudo-triangulation then the embedding will have exactly $`y`$ non-pointed vertices. In particular, the following statement is an indication that every planar and rigid graph can be embedded as a pseudo-triangulation:

###### Proposition 3.10.

Let $`G`$ be a planar and generically rigid graph with $`n`$ vertices and $`2n3+y`$ edges. Then, there is a subset $`Y`$ of cardinality $`y`$ of the vertices of $`G`$ such that every set of $`l`$ vertices in $`Y`$ plus $`k`$ vertices not in $`Y`$ is incident to at least $`2k+3l`$ edges, whenever $`k+ln2`$.

###### Proof.

Consider $`G`$ embedded planarly in a sufficiently generic straight-line manner. Since the embedding is planar, it can be completed to a pseudo-triangulation $`T`$. In particular, the set of edges of $`G`$ represents an independent subset of $`2n3+y`$ hyperplanes of $``$. But since the graph is rigid, adding marks to all the vertices produces a spanning set of $`3n3+y`$ hyperplanes. In between these two sets there must be a basis, consisting of the $`2n3+y`$ edges of $`G`$ plus $`ny`$ marks. We call $`Y`$ the vertices not marked in this basis, and the same argument as in the proof of Theorem 1.4 gives the statement. ∎

It has to be said however, that a planar graph $`G`$ with a subset $`Y`$ of its vertices satisfying Proposition 3.10 need not be generically rigid. Figure 8 shows an example (take as $`Y`$ any three of the four six-valent vertices).

## 4. Valid choices of $`f`$

It remains to be proved that valid choices of parameters do exist. In particular, that the choice in Theorem 3.7 is valid. Our methods, again inspired on , give actually more: a full description of the set of valid choices via a set of $`\left(\genfrac{}{}{0pt}{}{n}{4}\right)`$ linear inequalities, one for each 4-point subset of the $`n`$ points.

###### Definition 4.1.

Let $`G`$ be a graph embedded on $`𝒜`$, with set of edges $`E`$ and set of marked vertices $`V`$. In our context, a *stress* $`G`$ is an assignment of scalars $`w_{ij}`$ to edges and $`\alpha _j`$ to marked vertices of $`G`$, such that for every $`(v,t)^{3n}`$:

$$\underset{ijE}{}w_{ij}(p_ip_j,v_iv_j|p_ip_j|(t_i+t_j))+\underset{iV}{}\alpha _it_i=0$$
(6)
###### Lemma 4.2.

Let $`_{i=1}^n\lambda _ip_i=0`$, $`\lambda _i=0`$, be an affine dependence on a point set $`𝒜=\{p_1,\mathrm{},p_n\}`$. Then,

$$w_{ij}:=\lambda _i\lambda _j\text{ for every }i,j$$

and

$$\alpha _i:=\underset{j:ijE}{}\lambda _i\lambda _j|p_ip_j|\text{ for every }i$$

defines a stress of the complete graph $`G`$ on $`𝒜`$.

###### Proof.

The condition (6) on variables $`v`$ gives

$$\underset{ijE}{}w_{ij}p_ip_j,v_iv_j=0\text{, for every }v^{2n}$$
(7)
what can be equivalently stated as saying that the $`w_{ij}`$ form a stress on the underlying graph of $`G`$. This is fulfilled by the $`w_{ij}`$’s of the statement:

$$\underset{ji}{}\lambda _i\lambda _j(p_ip_j)=\underset{j=1}{\overset{n}{}}\lambda _i\lambda _j(p_ip_j)=\lambda _ip_i\underset{j=1}{\overset{n}{}}\lambda _j\lambda _i\underset{j=1}{\overset{n}{}}\lambda _jp_j=0$$

where last equality comes from $`\lambda _i`$’s being an affine dependence. Then, cancellation of the coefficient of $`t_i`$ in equation (6) is equivalent to $`\alpha _i=_{j:ijE}w_{ij}|p_ip_j|`$. ∎

Let us consider the case of four points in general position in $`^2`$, which have a unique (up to constants) affine dependence. The coefficients of this dependence are:

$$\lambda _i=(1)^idet([p_1,\mathrm{},p_4]\backslash \{p_i\})$$

Hence, if we divide the $`w_{ij}`$’s and $`\alpha _j`$’s of the previous lemma by the constant

$$det(p_1,p_2,p_3)det(p_1,p_2,p_4)det(p_1,p_3,p_4)det(p_2,p_3,p_4)$$

we obtain the following expressions:

$$w_{ij}=\frac{1}{det(p_i,p_j,p_k)det(p_i,p_j,p_l)},\alpha _i=\underset{j:ijE}{}w_{ij}|p_ip_j|$$
(8)
where, in that of $`w_{i,j}`$, $`k`$ and $`l`$ denote the two indices other than $`i`$ and $`j`$. The reason why we perform the previous rescaling is that the expressions obtained in this way have a key property which will turn out to be fundamental later on; see Figure 9:

###### Lemma 4.3.

For any four points in general position, the previous expressions give positive $`w_{ij}`$ and $`\alpha _j`$ on boundary edges and points and negative $`w_{ij}`$ and $`\alpha _j`$ on interior edges and points.

###### Proof.

In order to check the part concerning $`w_{ij}`$’s we use that $`det(q_1,q_2,q_3)`$ is two times the signed area of the triangle spanned by $`q_1,q_2,q_3`$: For a boundary edge the two remaining points lie on the same side of the edge, so they have the same sign. For an interior edge, they lie on opposite sides and therefore they have different signs.

For the $`\alpha _i`$’s, if $`i`$ is an interior point then all the $`w_{i,j}`$’s in the formula for $`\alpha _i`$ are negative and, hence, $`\alpha _i`$ is also negative. If $`i`$ is a boundary point then two of the $`w_{i,j}`$ are positive and the third one is negative. But, since

$$\underset{j\{1,2,3,4\}i}{}w_{i,j}(p_ip_j)=0,$$

the triangle inequality implies that the two positive summands $`w_{ij}|p_ip_j|`$ in the expression of $`\alpha _i`$ add up to a greater absolute value than the negative one. Hence $`\alpha _i`$ is positive. ∎

The previous statement is crucial to us, because no matter whether the four points are in convex position or one of them is inside the convex hull of the other three, the fully-marked pseudo-triangulations on the four points can be characterized as the marked graphs with nine edges plus marks and in which the missing edge or mark is interior (two f.m.p.t’s for points in convex position, four of them for a triangle plus an interior point).

We conclude that:

###### Theorem 4.4.

An $`f^{\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)}`$ is valid if and only if the following inequality holds for every four points $`\{p_1,p_2,p_3,p_4\}`$ of $`𝒜`$:

$$\underset{1i<j4}{}w_{ij}f_{ij}+\underset{j=1}{\overset{4}{}}\alpha _jf_{0j}>0$$
(9)
where the $`w_{ij}`$’s and $`\alpha _j`$’s are those of (8).

###### Proof.

Suppose first that $`𝒜`$ has only four points. The polyhedron $`\overline{Y_f}(𝒜)`$ is nine-dimensional, what implies that for every vertex $`(v,t)`$ of the polyhedron, the set $`T(v,t)`$ contains at least nine edges plus marks on those four points. Therefore, $`T(v,t)`$ is the complete marked graph with an edge or mark removed.

Let us denote by $`G_k`$ and $`G_{kl}`$ the complete marked graph with a non-marked vertex $`k`$ or a missing edge $`kl`$, respectively. Recall that by Lemma 4.3 the choice of stress on four points has the property that $`G_k`$ and $`G_{kl}`$ are fully-marked pseudo-triangulations if and only if $`\alpha _k`$ and $`w_{kl}`$ (corresponding respectively to the removed mark or edge) are negative. Let us see that this is equivalent to $`f`$ being valid:

By the definition of stress,

$$\underset{1i<j4}{}w_{ij}(p_ip_j,v_iv_j|p_ip_j|(t_i+t_j))+\underset{j=1}{\overset{4}{}}\alpha _jt_j$$

equals zero. In the case of $`G_k`$, in which every edge and vertex except $`k`$ are tight, that expression equals

$$\underset{1i<j4}{}w_{ij}f_{ij}+\underset{j=1}{\overset{4}{}}\alpha _jf_{0j}+\alpha _k(t_kf_{0k}).$$

In the case of $`G_{kl}`$, where every vertex and edge except $`kl`$ are tight, it equals

$$\underset{1i<j4}{}w_{ij}f_{ij}+\underset{j=1}{\overset{4}{}}\alpha _jf_{0j}+w_{kl}(p_kp_l,v_kv_l|p_kp_l|(t_k+t_l)f_{kl}).$$

Since $`p_kp_l,v_kv_l|p_kp_l|(t_k+t_l)f_{kl}0`$ and $`t_kf_{0k}0`$, by (4) and (5), we conclude that in the first and second cases above, $`\alpha _k`$ and $`w_{kl}`$ respectively are negative if, and only if, $`f`$ is valid.

Now we turn to the case of a general $`𝒜`$ and our task is to prove that a choice of parameters $`f`$ is valid if and only if it is valid when restricted to any four points. Observe that if $`𝒜^{}𝒜`$ then $`Y_f(𝒜^{})`$ equals the intersection of $`Y_f(𝒜)`$ with the subspace where $`v_i=0`$ and $`t_i=0`$ for all $`p_i𝒜𝒜^{}`$. In particular, the marked graphs on $`𝒜^{}`$ corresponding to faces of $`Y_f(𝒜^{})`$ are subgraphs of marked graphs of faces of $`Y_f(𝒜)`$. Moreover, non-crossingness of a marked graph on $`𝒜`$ is equivalent to non-crossingness of every induced marked graph on four vertices: indeed, a crossing of two edges appears in the marked graph induced by the four end-points of the two edges, and a non-pointed marked vertex appears in the marked graph induced on the four end-points involved in any three edges forming a non-pointed “letter Y” at the non-pointed vertex.

Hence: if $`f`$ is valid for every four points, then none of the 4-point minors forbidden by non-crossingness appear in faces of $`Y_f(𝒜)`$ and $`f`$ is valid for $`𝒜`$. Conversely, if $`f`$ is not valid on some four point subset $`𝒜^{}`$, then the marked graph on $`𝒜^{}`$ corresponding to any vertex of $`Y_f(𝒜^{})`$ would be the complete graph minus one boundary edge or vertex, that is to say, it would not be non-crossing. Hence $`f`$ would not be valid on $`𝒜`$ either. ∎

###### Corollary 4.5.

For any $`a,b^2`$, the choice $`f_{ij}:=det(a,p_i,p_j)det(b,p_i,p_j)`$, $`f_{0j}:=0`$ is valid.

###### Proof.

Consider the four points $`p_i`$ as fixed and regard $`R:=w_{ij}f_{ij}+\alpha _jf_{0j}=w_{ij}f_{ij}`$ as a function of $`a`$ and $`b`$:

$$R(a,b)=\underset{1i<j4}{}det(a,p_i,p_j)det(b,p_i,p_j)w_{ij}.$$

We have to show that $`R(a,b)`$ is always positive. We actually claim it to be always 1. Observe first that $`R(p_i,p_j)`$ is trivially 1 for $`ij`$. Since any three of our points are an affine basis and since $`R(a,b)`$ is an affine function of $`b`$ for fixed $`a`$, we conclude that $`R(p_i,b)`$ is one for every $`i\{1,2,3,4\}`$ and for every $`b`$. The same argument shows that $`R(a,b)`$ is constantly 1: for fixed $`b`$ it is an affine function of $`a`$ and is equal to 1 on an affine basis. ∎

## 5. Points in special position

In this section we show that almost everything we said so far applies equally to point sets with collinear points. We will essentially follow the same steps as in Sections 2, 3 and 4. Two subtleties are that our definitions of pointedness or pseudo-triangulations can only be fully justified a posteriori, and that the construction of the polyhedron for point sets with boundary collinearities is slightly indirect: it relies in the choice of some extra exterior points to make colliniarities go to the interior.

### The graph of all pseudo-triangulations of $`𝒜`$

###### Definition 5.1.

Let $`𝒜`$ be a finite point set in the plane, possibly with collinear points.

1. A graph $`G`$ with vertex set $`𝒜`$ is called *non-crossing* if no edge intersects another edge of $`G`$ or point of $`𝒜`$ except at its end-points. In particular, if $`p_1`$, $`p_2`$ and $`p_3`$ are three collinear points, in this order, then the edge $`p_1p_3`$ cannot appear in a non-crossing graph, independently of whether there is an edge incident to $`p_2`$ or not.
2. A *pseudo-triangle* is a simple polygon with only three interior angles smaller than 180 degrees. A *pseudo-triangulation* of $`𝒜`$ is a non-crossing graph with vertex set $`𝒜`$, which partitions $`\mathrm{conv}(𝒜)`$ into pseudo-triangles and such that no point in the interior of $`\mathrm{conv}(𝒜)`$ is incident to more than one angle of 180 degrees.

Figure 10 shows the eight pseudo-triangulations of a certain point set. We have drawn them connected by certain flips, to be defined later, and with certain points marked. The graph on the right of the figure is not a pseudo-triangulation because it fails to satisfy the last condition in our definition. Intuitively, the reason why we do not allow it as a pseudo-triangulation is that we are considering angles of exactly 180 degrees as being reflex, and we do not want a vertex to be incident to two reflex angles.

But if collinearities happen in the boundary of $`\mathrm{conv}(𝒜)`$, as in Figure 11, we treat things differently. The exterior angle of 180 degrees is not counted as reflex, and hence the middle point in a boundary collinearity is allowed to be incident to an interior angle of 180 degrees. The following definition can be restated as “a vertex is pointed if and only if it is incident to a reflex angle”, where reflex is meant as in these last remarks.

###### Definition 5.2.

A vertex $`p`$ in a non-crossing graph on $`𝒜`$ is considered *pointed* if either (1) it is a vertex of $`\mathrm{conv}(𝒜)`$, (2) it is semi-interior and not incident to any edge going through the interior of $`\mathrm{conv}(𝒜)`$ or (3) it is interior and its incident edges span at most 180 degrees.

A *non-crossing marked graph* is a non-crossing graph with marks at some of its pointed vertices. If all pointed vertices are marked we say the non-crossing graph is *fully-marked*. Marks at interior and semi-interior points will be called *interior marks*.

For example, all the graphs of Figures 10 and 11 are fully-marked. That is to say, big dots correspond exactly to pointed vertices. Of course, fully-marked pseudo-triangulations are just pseudo-triangulations with marks at all their pointed vertices. Observe that we are calling interior marks and edges exactly those which do not appear in all pseudo-triangulations. From now on, we denote by $`n_i`$, $`n_s`$ and $`n_v`$ the number of interior, semi-interior and extremal points of $`𝒜`$. Finally, $`n=n_v+n_s+n_i`$ denotes the total number of points in $`𝒜`$. The following two statements essentially say that Proposition 2.9 is valid for non-generic configurations.

###### Lemma 5.3.

Fully-marked pseudo-triangulations are exactly the maximal marked non-crossing graphs on $`𝒜`$. They all have $`3nn_s3`$ edges plus marks and $`2n_i+n3`$ interior edges plus interior marks.

###### Proof.

The first sentence is equivalent to saying that every non-crossing graph $`G`$ can be completed to a pseudo-triangulation without making any pointed vertex non-pointed. The proof of this is that if $`G`$ is not a pseudo-triangulation then either it has a face with more than three corners, in which case we insert the diagonal coming from the geodesic between any two non-adjacent corners, or there is an interior vertex with two angles of 180 degrees, in which case we choose to consider one of them as reflex and the other as convex, and insert the diagonal joining the convex angle to the opposite corner of the pseudo-triangle containing it.

To prove the cardinality of pseudo-triangulations, let $`n_ϵ`$ denote the number of marks. Let us think of boundary collinearities as if they were concave boundary chains in our graph, and triangulate the polygons formed by these chains by adding (combinatorially, or topologically) $`n_s`$ edges in total. If, in addition, we consider interior angles of 180 degrees or more as reflex and the others as convex, we get a graph with all the combinatorial properties of pseudo-triangulations and, in particular, a graph for which Proposition 2.2 can be applied, since its proof is purely combinatorial (a double counting of convex angles, combined with Euler’s relation). In particular, the extended graph has $`3n3`$ edges plus marks, and the original graph has $`3n3n_s`$ of them. Since there are exactly $`n_s+n_v`$ exterior edges and $`n_v`$ exterior marks in every pseudo-triangulation, the last sentence follows. ∎

###### Lemma 5.4.

If an interior edge or mark is removed from a fully-marked pseudo-triangulation then there is a unique way to insert another edge or mark to obtain a different fully-marked pseudo-triangulation.

###### Proof.

If an edge is removed then there are three possibilities: (1) the removal does not create any new reflex angle, in which case the region obtained by the removal is a pseudo-quadrangle (that is, it has four non-reflex angles), because the two regions incident to it had six corners in total and the number of them decreases by two. We insert the opposite diagonal of it. (2) the removal creates a new reflex angle at a vertex which was not pointed. Then the region obtained is a pseudo-triangle and we just add a mark at the new pointed vertex. (3) the removal creates a new reflex angle at a vertex that was already pointed. This means that after the removal the vertex has two reflex angles, that is to say two angles of exactly 180 degrees each. We insert the edge joining this vertex to the opposite corner of the pseudo-triangle containing the original reflex angle.

If a mark is removed, then the only possibility is: (4) the pointed vertex holding the mark is incident to a unique reflex angle (remember that we consider interior angles of 180 degrees as reflex). We insert the edge joining the vertex to the opposite corner of the corresponding pseudo-triangle. ∎

###### Definition 5.5.

Two fully-marked pseudo-triangulations are said to differ by a *flip* if they differ by just one edge or mark. Cases (1), (2), (3) and (4) in the previous proof are called, respectively, *diagonal flip*, *deletion flip*, *mirror flip* and *insertion flip*.

Of course, our definition of flips specializes to the one for points in general position, except that mirror flips can only appear in the presence of collinearities. An example of a mirror flip can be seen towards the upper right corner of Figure 10.

###### Corollary 5.6.

The graph of flips between fully-marked pseudo-triangulations of a planar point set is connected and regular of degree $`2n_i+n3`$.

The reader will have noticed that the graphs of Figures 10 and 11 are more than regular of degrees 4 and 3 respectively. They are the graphs of certain simple polytopes of dimensions 4 and 3. (Figure 10 is a prism over a simplex).

### The case with only interior collinearities

Now we assume that our point set $`𝒜`$ has only interior collinearities.

For each $`f^{n+1}`$ let $`\overline{Y_f}(𝒜)`$ be the polyhedron defined in Section 3. Recall that everything we said in that section, up to Corollary 3.5, is valid for points in special position. Our main result here is that Theorems 3.7 and 3.8 hold word by word in the case with no boundary collinearities, except that a precision needs to be made regarding the concept of validity.

Recall that for a given choice of $`f^{\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)}`$, an edge $`p_ip_j`$ or a point $`p_i`$ are called *tight* for a certain $`(v,t)^{3n3}`$ or for a face $`F`$ of $`\overline{Y_f}(𝒜)`$ if the corresponding equation (4) or (5) is satisfied with equality.

###### Definition 5.7.

We call *strict supporting graph* of a $`(v,t)^{3n3}`$ (or face $`F`$ of $`\overline{Y_f}(𝒜)`$) the marked graph of all its tight edges and points, and denote it $`T(v,t)`$. We call *weak supporting graph* of a $`(v,t)`$ or face the marked subgraph consisting of edges and points of $`T(v,t)`$ which define facets of $`\overline{Y_f}(𝒜)`$.

A choice of $`f`$ is called *weakly valid* (resp., *strictly valid*) if the weak (resp., strict) supporting graphs of all the faces of $`\overline{Y_f}(𝒜)`$ are non-crossing marked graphs.

Observe that from any weakly valid choice $`f`$ one can obtain strictly valid ones: just decrease by arbitrary positive amounts the coordinates of $`f`$ corresponding to equations which do not define facets of $`\overline{Y_f}(𝒜)`$. Hence, we could do what follows only in terms of strict validity and would obtain the same polyhedron. But weak validity is needed, as we will see in Remark 5.13, if we want our construction to depend continuously on the coordinates of the point set $`𝒜`$.

To obtain the equations that valid choices must satisfy we proceed as in Section 4. The crucial point there was that a marked graph is non-crossing if and only if it does not contain the negative parts of the unique stress in certain subgraphs.

###### Lemma 5.8.

Let $`𝒜`$ be a point set with no three collinear boundary points. Then, a marked graph on $`𝒜`$ is non-crossing if and only if it does not contain any of the following four marked subgraphs: the negative parts of the marked graphs displayed in Figure 9 and the negative parts of the marked graphs displayed in Figure 12.

###### Proof.

Exclusion of the negative parts of the left graphs in both figures are our definition of crossingness for an unmarked graph. An interior vertex is pointed if and only if none of the negative parts of the right graphs appear. ∎

###### Lemma 5.9.

The two graphs in Figure 12 have a stress with signs as in the figure.

###### Proof.

For the left part it is easy to show that the following is a stress:

$$w_{12}=\frac{1}{|p_2p_1|},w_{13}=\frac{1}{|p_3p_1|},w_{23}=\frac{1}{|p_3p_2|},\alpha _1=\alpha _3=0,\alpha _2=2.$$

For the right part, observe that, by definition, stresses on a marked graph form a linear space. Let the four exterior points be $`p_1`$, $`p_2`$, $`p_3`$ and $`p_4`$, in cyclic order, and let the interior point be $`p_5`$. We know three different stresses of the complete graph on these five points: the one we used in Section 4 for the four exterior points and the two that we have just introduced for the two collinear triplets. From these three we can eliminate the coordinates of edges $`p_1p_3`$ and $`p_2p_4`$ and we get a stress with the stated signs. ∎

###### Theorem 5.10.

Let $`𝒜`$ be a point set with no three collinear boundary points. Then, a choice of $`f`$ is weakly valid if it satisfies equations (9) for all quadruples of points in general position plus the following sets of equations:

* For any three points $`p_1`$, $`p_2`$ and $`p_3`$ collinear in this order:

$$\frac{f_{12}}{|p_2p_1|}\frac{f_{13}}{|p_3p_1|}+\frac{f_{23}}{|p_3p_1|}+2f_{02}0$$
(10)
* For any five points as in the right part of Figure 12, the following equation where the $`w_{ij}`$’s and the $`\alpha _i`$’s form a stress with signs as indicated in the figure (by convention, $`w_{ij}`$ equals zero for the two missing edges in the graph):

$$\underset{1i<j5}{}w_{ij}f_{ij}+\underset{j=1}{\overset{5}{}}\alpha _jf_{0j}>0$$
(11)

The choice is strictly valid if and only if, moreover, the equations (10) of all collinear triplets are satisfied strictly.

###### Proof.

Equations (9) guarantee that no weak or strict tight graph contains the two excluded marked graphs of negative edges and points of Figure 9. Equations (10) and (11) with strict inequality, do the same for the graphs of Figure 12. That these equations are equivalent to strict validity is proved exactly as in Section 4. The reason why we allow equality in equations (10) if we only want a weakly valid choice is that the negative part of the stress consists of a single edge. If the equation is satisfied with equality then the hyperplane corresponding to this edge is a supporting hyperplane of the face of $`\overline{Y_f}`$ given by the intersection of the three hyperplanes of the positive part of the stress. ∎

###### Corollary 5.11.

Let $`𝒜`$ be a point set with no collinear boundary points. Any choice of $`f`$ satisfying equations (9) for every four points in general position plus the following ones for every collinear triplet is weakly valid:

$$\frac{f_{12}}{|p_2p_1|}\frac{f_{13}}{|p_3p_1|}+\frac{f_{23}}{|p_3p_1|}+2f_{02}=0$$
(12)
In particular, the choices of Corollary 4.5 and Theorem 3.7 are weakly valid.

###### Proof.

For the first assertion, we need to show that equations (11) follow from equations (9) and (12). But this is straightforward: from our proof of Lemma 5.9 it follows that equation (11) is just the one obtained substituting in (9) the values for $`w_{13}`$ and $`w_{24}`$ obtained from the two equations (12).

For the last assertion, we already proved in Corollary 4.5 that the choices of $`f`$ introduced there satisfy equations (9). It is easy, and left to the reader, to show that they also satisfy (12). ∎

###### Theorem 5.12.

(Main theorem, case without boundary collinearities) Let $`𝒜`$ be a point set with no three collinear points in the boundary of $`\mathrm{conv}(𝒜)`$, and let $`f`$ be a weakly valid choice of parameters. Then, $`\overline{Y_f}`$ is a simple polyhedron of dimension $`3n3`$ with all the properties stated in Theorems 3.8 and 3.9.

###### Proof.

Recall that if no three boundary points are collinear then every fully-marked pseudo-triangulation (i.e., maximal marked non-crossing graph) has $`3n3`$ edges plus marks, exactly as in the general position case (Lemma 5.3). In particular, it is still true, for the same reasons as in the general position case, that $`\overline{Y_f}(𝒜)`$ is simple and all its vertices correspond to f.m.p.t.’s, for any valid choice of $`f`$. The rest of the arguments in the proof of Theorem 3.8 rely on the graph of flips being connected, a property that we still have. As for Theorem 3.9, the face $`Y_f(𝒜)`$ is bounded because Lemma 3.3 still applies. The rest is straightforward. ∎

###### Remark 5.13.

It is interesting to observe that taking the explicit valid choice of $`f`$ of Theorem 3.7 the equations defining $`\overline{Y_f}(𝒜)`$ depend continuously on the coordinates of the points in $`𝒜`$. When three points become collinear, the hyperplane corresponding to the (now) forbidden edge becomes, as we said in the proof of Theorem 5.10 a supporting hyperplane of a codimension 3 face of $`\overline{Y_f}(𝒜)`$. The combinatorics of the polytope changes but maintaining its simplicity. This continuity of the defining hyperplanes would clearly be impossible if we required our choice to be strictly valid for point sets with collinearities.

###### Example 5.14.

Let $`𝒜_1`$ and $`𝒜_2`$ be the two point sets with five points each whose pseudo-triangulations are depicted in Figures 13 and 14. The first one has three collinear points and the second is obtained by perturbation of the collinearity. These two examples were computed with the software CDD+ of Komei Fukuda  before we had a clear idea of what the right definition of pseudo-triangulation for points in special position should be. To emphasize the meaning of weak validity, in Figure 13 we are showing the weak supporting graphs of the vertices of $`\overline{Y_f}(𝒜_1)`$, rather than the strict ones.

The 10 first pseudo-triangulations are common to both figures (upper two rows). Only the pseudo-triangulations of $`𝒜_1`$ using the two collinear edges plus the mark at the central point of the collinearity are affected by the perturbation of the point set. This is no surprise, since these two edges plus this mark are the positive part of the stress involved in the collinearity. At each of these six pseudo-triangulations, the hyperplane of the big edge is tangent to the vertex of $`\overline{Y_f}(𝒜_1)`$ corresponding to the pseudo-triangulation. When the collinearity is perturbed, this hyperplane moves in one of the two possible ways: away from the polyhedron, in which case the combinatorics is not changed, or towards the interior of the polyhedron, in which case the old vertex disappears and some new vertices are cut by this hyperplane. In our case, these two behaviors appear each in three of the six “non-strict” pseudo-triangulations of $`𝒜_1`$. When the hyperplane moves towards the interior, four new vertices appear where there was one.

### Boundary collinearities

In the presence of boundary collinearities, Lemma 5.3 implies a significant difference: with the equations we have used so far, the face of $`\overline{Y_0}(𝒜)`$ defined by tightness at boundary edges and vertices is not the origin, but an unbounded cone of dimension $`n_s`$. Indeed, for each semi-interior point $`p_i`$, the vector $`(v,t)`$ with $`v_i`$ an exterior normal to the boundary of $`\mathrm{conv}(𝒜)`$ at $`p_i`$ and every other coordinate equal to zero defines an extremal ray of that face. As a consequence, the corresponding face in $`\overline{Y_f}(𝒜)`$ is unbounded.

We believe that it should be possible to obtain a polyhedron with the properties we want by just intersecting the polyhedron of our general definition with $`n_s`$ hyperplanes. But instead of doing this we use the following simple trick to reduce this case to the previous one. From a point set $`𝒜`$ with boundary collinearities we construct another point set $`𝒜^{}`$ adding to $`𝒜`$ one point in the exterior of each edge of $`\mathrm{conv}(𝒜)`$ that contains semi-interior points.

###### Lemma 5.15.

A marked graph $`G`$ on $`𝒜`$ is non-crossing if and only if it becomes a non-crossing graph on $`𝒜^{}`$ when we add to it the marks on all points of $`𝒜^{}𝒜`$ and the edges connecting each of these points to all the points of $`𝒜`$ lying in the corresponding edge of $`\mathrm{conv}(𝒜)`$.

###### Proof.

Straightforward. ∎

In particular, we can construct the polyhedron $`\overline{Y_f}(𝒜^{})`$ for this extended point set $`𝒜^{}`$ (taking any $`f`$ valid on $`𝒜^{}`$), and call $`\overline{Y_f}(𝒜)`$ the face of $`\overline{Y_f}(𝒜^{})`$ corresponding to the edges and marks mentioned in the statement of Lemma 5.15. Then:

###### Corollary 5.16.

(Main theorem, case with boundary collinearities) $`\overline{Y_f}(𝒜)`$ is a simple polyhedron of dimension $`3n3n_s`$ with all the properties stated in Theorem 3.8.

Let $`Y_f(𝒜)`$ be the face of $`\overline{Y_f}(𝒜)`$ corresponding to the $`n_v+n_s`$ edges between consecutive boundary points and the $`n_v`$ marks at vertices of $`\mathrm{conv}(𝒜)`$. Let $`F`$ be the face of $`Y_f(𝒜)`$ corresponding to the remaining $`nn_v`$ marks. Then, $`Y_f(𝒜)`$ is a polytope of dimension $`2n_i+n3`$ and $`F`$ is a face of it of dimension $`2n_i+n_v3`$. They satisfy all the properties stated in Theorem 3.9.

###### Remark 5.17.

The reader may wonder about the combinatorics of the polyhedron $`\overline{Y_f}(𝒜)`$ that one would obtain with the equations of the generic case. Clearly, the tight graphs of its faces will not contain any of the four forbidden subgraphs of Lemma 5.8. It can be checked that the maximal marked graphs without those subgraphs all have $`3n3`$ edges plus marks and have the following characterization: as graphs they are pseudo-triangulations in which all the semi-interior vertices are incident to interior edges, and they have marks at all the boundary points and at the pointed interior points. In other words, they would be the fully-marked pseudo-triangulations if we treated semi-interior points exactly as interior ones, hence forbidding them to be incident to two angles of 180 degrees and considering them always pointed since they are incident to one angle of 180 degrees.

For example, in the point set of Figure 11 there are 6 such graphs, namely the ones shown in Figure 16.

This implies that the polyhedron $`\overline{Y_f}(𝒜)`$ is still simple. The reason why we prefer the definitions we have given is that the polyhedron no longer has a unique maximal bounded face (it has three in the example of Figure 16) and the graph of flips is no longer regular.

Observe finally that the proof of Theorem 1.4 given at the end of Section 3 is valid for points in special position, without much change: in all cases the hyperplanes corresponding to the edges of a pseudo-triangulation are independent in $`\overline{Y_0}(𝒜)`$.


format: text

text:
# 1 Introduction and relation to previous work

## 1 Introduction and relation to previous work

Recently, we have argued that the vanishing of the vacuum energy of $`(2+1)`$-dimensional gravity  may be deconstructed  to $`3+1`$ dimensions under certain conditions . Our discussion pointed towards a possibility that there exists a well-defined UV completion of $`(3+1)`$-dimensional gravity. (For related discussions, see Refs.  and .)

More recently it was pointed out by Arkani-Hamed and Schwartz  that the physics of gravitational deconstruction exhibits a fascinating relation between the characteristic UV and IR scales. This UV/IR relation was argued  to indicate the presence of non-local interactions in the defining UV theory.

Here, we point out that the UV/IR relation found in Ref.  is nothing but a manifestation of the holographic principle . In particular the specific form of the UV/IR correspondence found in the problem of deconstruction of gravity is very analogous to a similar relation found  in a seemingly completely unrelated topic - the AdS/CFT correspondence  (see also )!

As reviewed in Ref. , in $`(2+1)`$-dimensional theories it is possible  to have vanishing vacuum energy in the absence of a mass degenerate spectrum of bosonic and fermionic states. The basic point is that the vacuum state is supersymmetric, but the excited states are not mass degenerate because unbroken global supercharges do not exist in $`2+1`$ dimensions . Any excited state gives a conical geometry whose deficit angle prohibits spinor fields with covariantly constant asymptotics. Thus, there are no global supercharges and no mass degeneracy between Bose and Fermi excitations. The size of the non-degeneracy of the spectrum of low-energy excitations scales as the inverse power of the three-dimensional Newton constant under the assumption of weak gravitational coupling .

The idea behind deconstruction  is that the UV region of a theory might be described in terms of a co-dimension one theory. Motivated by this idea in Ref.  we argued that the $`(2+1)`$-dimensional phenomenon described above can be deconstructed as follows:

* (1) Assume a local spatial foliation of 4d spacetime.
* (2) Deconstruct the vacuum part of pure 4d gravity from ($`N`$ copies of) 3d general relativity  coupled to certain 3d matter fields represented in terms of currents. Assume that the 4d sources can be defined in terms of a deconstructed 3d theory. For sources represented by gauge fields this should be possible given the discussion in Ref. .
* (3) In the deep UV we have ($`N`$ copies of) 3d gravity coupled to some 3d sources. Whatever the matter content of this 3d theory is, the resulting geometry has to be conical. Thus, provided we have 3d (but not 4d!) supersymmetry, Witten’s argument applies: the vacuum is supersymmetric, yet the excited states are not.
* (4) In the range of intermediate scales, we have $`N`$ linked copies of 3d gravity coupled to 3d currents. Once again, the resulting 3d geometry is conical. Thus Witten’s argument holds in the region between the UV and IR.

Note that on dimensional grounds, the mass splitting should be inversely proportional to the three-dimensional Newton constant and should vanish at zero deficit angle.Thus as long as the three-dimensional Newton constant is of order one as the continuum limit is taken, and the deficit angle (on each local three-dimensional slice) is taken to scale as the inverse of the lattice spacing, the Bose-Fermi splitting will be finite in the infrared.

According to the outlined argument the vacuum energy is zero in the UV, and also some place in between UV and IR. But does it remain zero in the IR? In the concluding part of this note, we remark that the UV/IR relation found in Ref. , which as we argue is just the statement of the saturation of the holographic bound, can be utilized to put an upper bound on the maximum value of the deconstructed cosmological constant.

## 2 Holography and Deconstruction

Before we proceed to establish a relation between the UV/IR correspondence found in Ref.  and the holographic bound it is useful to remember how holography arises in the framework of our previous paper .

The Bekenstein-Hawking bound on entropy  arises as follows. Let us first suppose that the $`(2+1)`$-dimensional matter fields are local. The coupling of $`(2+1)`$-dimensional gravity to matter is of the general form

$$S_{EH}=\frac{1}{G_3}d^3x\sqrt{g^{(3)}}(R^{(3)}+_{\mathrm{matter}}).$$
(1)
The entropy of local matter degrees of freedom scales as the two-dimensional area. As there are $`N`$ copies, we have

$$𝒮\frac{NA}{G_3}.$$
(2)
Obviously this expression does not have the correct mass dimension. The crucial step at this point is to remember that the usual prescription for dimensional reduction determines the pre-factor to be $`1/G_3L`$, where $`L=Na`$ is the size of the fourth (lattice) dimension. Thus, on dimensional grounds,

$$𝒮\frac{NA}{G_3L}=\frac{A}{G_3a}=\frac{A}{G_4},$$
(3)
which reproduces the Bekenstein-Hawking scaling in $`3+1`$ dimensions.

Note that this reasoning applies only in the case of 3d to 4d, where there are no local gravitational degrees of freedom. We wish now to relate this scaling to the UV/IR relation found in Ref. . The latter result is stronger, applying in any dimension.

## 3 Deconstruction and UV/IR mixing

As argued by Arkani-Hamed and Schwartz in a recent paper , there exists a subtlety in the implementation of deconstruction in the gravitational context. Namely, the cutoff of the theory cannot be taken to be $`M_4`$, the four-dimensional Planck scale, as one would expect. A simple tree-level calculation indicates that instead, there are amplitudes involving longitudinal components of gravitons which de-unitarize around a scale

$$\mathrm{\Lambda }\left(\frac{M_4^2}{L^5a^2}\right)^{1/9},$$
(4)
where $`L=Na`$, $`a`$ being the lattice spacing, and $`G_4=G_3a`$, as in Ref. . This result seems to be indicative of a UV/IR mixing phenomenon. Indeed, when one looks more closely at the details of the effective action for the interactions, one finds that one may indeed interpret it as non-local.

In fact, if we require that the cutoff be above the most massive Kaluza-Klein states but below the unitary threshold, one finds that the highest cutoff that the theory may possess is of order

$$\mathrm{\Lambda }_m\left(\frac{M_4^2}{L}\right)^{1/3}.$$
(5)
This scale has an important implication in terms of holography. To demonstrate this, consider a calculation of entropy. In the four-dimensional theory, we would estimate

$$𝒮AL\mathrm{\Lambda }^3,$$
(6)
which would give the standard wrong result if $`\mathrm{\Lambda }M_4`$. With the cutoff of eq. (5), we find instead111Here we used the thermodynamic relation $`𝒮VT^3`$ where the volume $`VAL`$ and $`T\mathrm{\Lambda }_m`$, by construction.

$$𝒮AL\mathrm{\Lambda }_m^3\frac{NA}{G_3L}\frac{A}{G_4},$$
(7)
which is nothing but the holographic bound on the number of degrees of freedom in the UV theory, as it should be if the theory is really expected to describe a UV definition of gravitational 4d dynamics. The deconstructed theory resists the temptation to lift its cutoff too high. It appears that unitarity plus diffeomorphism invariance are sufficient to imply holography! As indicated above, this argument generalizes to any number of dimensions.

As an aside, it is interesting to observe that the above expression for the holographic bound is reminiscent of the one obtained from the heuristic argument based on the properties of gravitational focusing . Given a boundary region of area $`A`$, the number of UV degrees of freedom is estimated from the effective volume determined by the area and the Planck length $`AL_P`$ and the UV cut-off given by $`1/L_P^3`$ which combines into the holographic (Bekenstein-Hawking) bound $`A/L_P^2`$.222We thank Nemanja Kaloper for an enjoyable discussion concerning these heuristics.

Notice that this kind of relation between a UV/IR correspondence and holography is in complete analogy to what happens in the context of the AdS/CFT correspondence, even though the two topics seem unrelated. Taking clues from the AdS/CFT correspondence, we also see that the UV/IR mixing found in the context of gravitational deconstruction can be interpreted locally. That is, the local rescaling in the UV theory corresponds to the rescaling of the size of the extra dimension: the UV Wilsonian evolution corresponds to the gravitational evolution in the extra dimension.

More explicitly, a local form of the UV/IR correspondence can be recast in the form of a holographic RG formalism even in the present discussion of the deconstruction of gravity.

This formalism runs as follows . First we fix the gauge so that the bulk metric can be written as

$$ds^2=dr^2+g_{ij}dx^idx^j.$$
(8)
This is just the ADM gauge discussed both in Ref. : the shift vector is set to zero and the lapse to one. As noticed above, the UV rescaling corresponds to the rescaling in the size of the extra dimension, which in the chosen gauge is nothing but the natural evolution parameter. Given the fact that the $`(3+1)`$-dimensional gravity theory is reparametrization invariant, the local UV rescaling is encapsulated in the IR by the four-dimensional Hamiltonian constraint

$$=0.$$
(9)
More explicitly

$$=(\pi ^{ij}\pi _{ij}\frac{1}{2}\pi _i^i\pi _j^j)+\frac{1}{2}\pi _IG^{IJ}\pi _J+.$$
(10)
Here $`\pi _{ij}`$ and $`\pi _I`$ are the canonical momenta conjugate to $`g^{ij}`$ and $`\varphi ^I`$

$$\pi _{ij}=\frac{1}{\sqrt{g}}\frac{\delta S}{\delta g^{ij}},\pi _I=\frac{1}{\sqrt{g}}\frac{\delta S}{\delta \varphi ^I}.$$
(11)
Here $`\varphi ^I`$ denotes some background matter fields coupled to $`(3+1)`$-dimensional gravity — for example, the Standard model fields; $``$ is a local Lagrangian density, and $`G^{IJ}`$ denotes the metric on the space of background matter fields.

As in the context of the AdS/CFT duality , the Hamiltonian constraint can be formally rewritten as a renormalization group equation for the dual RG flow.333Here we follow the formalism of Ref. . In the Hamiltonian constraint

$$\frac{1}{\sqrt{g}}\left(\frac{1}{2}\left(g^{ij}\frac{\delta S}{\delta g^{ij}}\right)^2\frac{\delta S}{\delta g^{ij}}\frac{\delta S}{\delta g_{ij}}\frac{1}{2}G^{IJ}\frac{\delta S}{\delta \varphi ^I}\frac{\delta S}{\delta \varphi ^I}\right)=\sqrt{g},$$
(12)
assume that the local four-dimensional action $`S`$ can be separated into a local and a non-local piece

$$S(g,\varphi )=S_{loc}(g,\varphi )+\mathrm{\Gamma }(g,\varphi ).$$
(13)
Given this rewriting of the four-dimensional action, the Hamiltonian constraint can be formally rewritten as a Callan-Symanzik renormalization group equation for the effective action  $`\mathrm{\Gamma }`$ of the UV theory at the scale $`\mathrm{\Lambda }`$

$$\frac{1}{\sqrt{g}}\left(g^{ij}\frac{\delta }{\delta g^{ij}}\beta ^I\frac{\delta }{\delta \varphi ^I}\right)\mathrm{\Gamma }=HO,$$
(14)
where $`HO`$ denotes higher derivative terms of the expression for the four-dimensional conformal anomaly. Here the “beta-function” is defined (in analogy with the AdS situation) to be $`\beta ^I=_\mathrm{\Lambda }\varphi ^I`$, where $`\mathrm{\Lambda }`$ denotes the cut-off of the defining UV theory.

In the context of the holographic RG formalism developed in the AdS/CFT correspondence, it is also possible to introduce a holographic “c-function” which measures the number of accessible degrees of freedom and which decreases during RG flow. When the spacetime is four-dimensional, one has

$$c\frac{1}{G\theta ^2},$$
(15)
where $`\theta `$ is the trace of the extrinsic curvature of the boundary surface.444The trace of the quasi-local Brown-York stress  tensor turns out to be $`T_i^i\theta `$, up to some terms constructed from local intrinsic curvature invariants of the boundary. Therefore the RG equation of the defining UV theory is given by $`T_i^i=\beta ^I\frac{\mathrm{\Gamma }}{\varphi ^I}`$. In the context of the AdS/CFT correspondence the Raychauduri equation, that is, gravitational focusing, implies monotonicity of the holographic “c-function”

$$\frac{d\theta }{dt}0,$$
(16)
as long as a form of the weak positive energy condition is satisfied by the background test matter fields.

The important point here is that the holographic “c-function” is determined by the holographic bound, that is the Bekenstein-Hawking entropy. In our context the Bekenstein-Hawking entropy is determined by $`AL\mathrm{\Lambda }_m^3`$. Thus at a scale $`\mathrm{\Lambda }`$ below the maximal scale, the natural expression for the holographic “c-function” in the present context is precisely the quantity

$$cAL\mathrm{\Lambda }^3$$
(17)
which measures the number of degrees of freedom in the UV theory.

## 4 Conclusion: UV/IR, cosmological constant, non-local interactions and all that

The argument for the vanishing of the cosmological constant in $`(3+1)`$-dimensional gravity as presented in Ref.  is obscured by the region of strong coupling in the infrared. The question is whether the cosmological constant remains zero all the way at long distances even in the presence of strongly coupled physics. In the conclusion of this note, we argue that one can actually derive the upper bound on the value of the induced four-dimensional vacuum energy based on the above discussion regarding the relation deconstruction and holography.

The essential point is that the picture of vacuum energy based on deconstruction  naturally presents us with two different energy scales in the IR. One scale is the mass splitting between fermion and bosonic degrees of freedom $`M_s`$, indicating the crucial importance of supersymmetry in our argument , and the other is the four-dimensional Planck scale $`M_P`$. These two scales come from the two dimensionful parameters provided by the UV definition of the infrared physics via deconstruction: the lattice spacing $`a`$ and the three-dimensional Newton’s constant $`G_3`$ .

Now, given these two mass scales and the requirement that in the limit when the mass splitting of the bosonic and fermionic degrees of freedom goes to zero, the four-dimensional vacuum energy should go to zero as well, we can associate one four-dimensional scale $`m`$ with $`M_s`$ and $`M_P`$. This scale will provide the natural cut-off in the computation of the four-dimensional vacuum energy.

Dimensional analysis and the requirement that $`m0`$ when $`M_s0`$ dictates that

$$m\frac{M_s^2}{M_P}.$$
(18)
This, we claim, is the only effective UV scale left in the problem in four dimensions. Notice that this relation is also a manifestation of a UV/IR correspondence. The $`M_P`$ is already an IR scale from the point of view of the defining UV theory. That follows from the relation $`G_4=G_3a`$. As we approach the continuum, the three-dimensional scale is much higher than the effective four-dimensional gravitational scale. Now, given the fact that the effective action contains fields coupled to four-dimensional gravity, one expects that the natural cut-off scale $`m`$ goes as an inverse power of the IR scale, which is set by the Planck scale $`M_P`$, and the scale $`M_s`$ that governs the Bose-Fermion mass splitting. The quadratic scaling of $`m`$ with $`M_s`$ is determined by the gravitational coupling of the matter fields at the scale $`M_s`$. (By the deconstruction of Witten’s argument , the vacuum energy is still zero at this scale.) Then the above formula indeed follows by dimensional analysis.

When evaluating the vacuum diagrams in order to estimate the upper bound on the vacuum energy in the infrared we should therefore use $`m`$ as the only effective cut-off scale. The naive expression for the vacuum energy is bounded by $`m^4`$ or

$$\lambda M_P^4\left(\frac{M_s}{M_P}\right)^8,$$
(19)
which is a formula previously discussed in the literature . Therefore, provided the large ratio of the mass splitting to the Planck scale we get the observed bound on the vacuum energy density!

Note that this argument is based on dimensional analysis, the UV/IR relation discussed above, and the fact that the deconstruction of Witten’s argument for the vanishing of the cosmological constant in three dimensions implies zero vacuum energy at a very low scale, set by the value of $`M_s`$. The violation of the usual effective field theory reasoning comes from the UV/IR relation and the vanishing of the cosmological constant at the scale determined by $`M_s`$, as implied by the deconstruction of Witten’s argument.

Of course, we have not presented a detailed calculation, and it is not completely clear if $`m^4`$ really determines the cosmological constant. Also, one should carefully consider radiative corrections. Given the fact that the cosmological constant vanishes at the scale determined by $`M_s`$ by deconstruction, the radiative corrections determined by usual effective field theory, cannot be expected to be very large. It is desirable therefore to provide an explicit calculation to show this.

In concluding, we raise the question of whether the non-local interaction expected in the UV theory  should be of the type discussed in the “wormhole” program . The idea here is that a guiding principle for the construction of a defining UV theory should be the recovery of the full path integral over four-dimensional metrics in the IR. This, at least at the level of Euclidean gravity, can be implemented by an insertion of bilocal operators which create “wormholes”. It was shown in the late 80’s  that such topology changing processes make all couplings in the Wilsonian effective action describing the interaction of gravity and matter into true dynamical random variables. It would be interesting to see whether there is a natural implementation of this idea in the present context.

## Acknowledgments

We thank Vijay Balasubramanian and Nemanja Kaloper for conversations and comments. VJ thanks the High Energy Group at the University of Pennsylvania for their kind hospitality. RGL thanks the Instituto de Física Teórica de la Universidad Autónoma de Madrid for their kind hospitality. DM thanks the Cosmology Group of the University of California at Davis for their kind hospitality. This work is supported in part by the U.S. Department of Energy under contracts DE-FG02-91ER40677 and DE-FG05-92ER40709.


text:
# Velocity Dispersion in the Halo of 𝜔 Centauri: No need for MOND given the present data

## References

Anderson, A. J. 1997, PhD Thesis, University of California (Berkeley)

King, I. R. 1966, AJ, 71, 64

King, I. R., & Anderson, J. 2002, in ASP Conf. Ser. 265, ed. F. van Leeuwen, J. Hughes, and G. Piotto (San Francisco: ASP), p. 21

Meylan, G. 1987, A&A, 184, 144

Meylan, G., Mayor, M., Duquennoy, A., & Dubath, P. 1995, A&A, 303, 761

Merritt, D., Meylan, G., & Mayor, M., 1997, AJ, 114, 1074

Milgrom, M. 1983, ApJ, 270, 365

Scarpa, R., Marconi, G., & Gilmozzi, R. 2003, these proceedings (astro-ph/0208061)

Seitzer, P. O. 1983, PhD Thesis, University of Virginia

van Leeuwen, F., Le Poole, R. S., Reijns, R. A., Freeman, K. C., & de Zeeuw, P. T. 2000, A&A, 360, 472

Wilson, C. P. 1975, AJ, 80, 175


text:
# Untitled Document

This paper has now been withdrawn.