Hence we can give a first result on the monotonicity of a tree:

Now let's discuss the computation of monotonic trees.

Let MD(v) be the set of directions for which v is a minimum for EA(v). Now consider the half-spaces delimited by the plan formed by v and its normal d and oriented according to d as shown on the next picture.

If we assume T monotonic with respect to d, it means that r, the root, is the only proper minimum, and no other vertex is a local minimum with respect to d. By the previous lemma, d cannot be contained in MD(v) for all vertices of T other than the root. Hence, what do we need to check? We have to verify if d is contained in MD(v). To say it in another way, we have to check if for every edge leaving v, v is a minimum with respect to d for EA(v). The only question is: how many edges leave v? or what is the degree of v in T? Since we have to check every vertex, and the sum of the degree is linear to the number of vertices, we can compute what we want in O(n) time.

We just find a way of solving our problem with a rooted tree. What if the root is not specified? We must find it first before checking the monotonicity of the tree. It could be done easily since the potential root is the only vertex which is supposed to be a proper local minimum, and d cannot be in the closure of MD(v) for any other vertices of T. This could be verified in linear time.

Given an unrooted tree T, could we find all the roots and directions with respect to which T is monotonic?

To answer this question, we need to introduce a new way of representing directions of projections. Imagine a cube centered on a vertex v, and each point p on the vertex represents the direction vp.

Let's take any vertex v. As mentioned earlier, the intersection of MD(v) and the cube represents the directions for which v is a proper local minimum. MD(v) intersects the cube with each facet under three different forms:

• An empty space.
• The entire facet.
• A convex polygon.

To understand the demonstration completely, we have to imagine all the vertices and their associated MD(v) concentrated in the center of the cube and imagine all the intersections on the facets of the cube. Now it is interesting to watch a point on a facet, which represents a direction, and check if it is inside one or several polygons defined above. For example, if one point p is in the interior of k polygons, there are k vertices of T that are local minimum, with respect to Op. One facet is shown as an example in the next picture:

How to compute the set of directions?

Now that we know what to look for with such a representation, it seems essential to know how to compute it.
For every facet F_i of the cube, we can create the subdivision A_i composed of all the polygons which are intersections of MD(v_i) and the facets.

For every cell of A_i there exists a node and an edge between two nodes if the cells are adjacent. The graph G_i (planar dual graph of A_i) has O(n²) edges and nodes. We have to associate every nodes to the number of polygons which are covering it. Thus starting at any node, we can go to another node through an edge, adding or subtracting one to the previous number of polygons and assigning the number to the node. This procedure can be done in O(n²) time according to the number of nodes and edges in the subdivision. Let's consider the cell covered by only one polygon, all these cells represent a set of directions and a root from which T is monotonic. The root of T is specified by the vertex generating the convex polygon covering the cell.