Efficient Boundary Extraction from Orthogonal Pseudo-Polytopes: An Approach Based on the nD-EVM

1. Introduction

The extreme vertices model in the n-dimensional space (nD-EVM) is a representation scheme whose dominion is given by the n-dimensional orthogonal pseudo-polytopes, that is, polytopes that can be seen as a finite union of iso-oriented nD hyperboxes (e.g., hypercubes). The fundamental notions of the model, for representing 2D and 3D-OPPs, were originally established by Aguilera and Ayala in [1, 2]. Then, in [3], it was formally proved the model is capable of representing and manipulating nD-OPPs. The nD-EVM has a well-documented repertory of algorithms (see [1, 3–7]) for performing tasks such as Regularized Boolean operations, set membership classification, measure interrogations (content and boundary content), morphological operations (e.g., erosion and dilation), geometrical and topological interrogations (e.g., discrete compactness), among other algorithms currently being in development. Furthermore, conciseness, in terms of spatial complexity, is one the nD-EVM’s main properties, because the model only requires storing a subset of a polytope’s vertices, the extreme vertices, which finally provides efficient temporal complexity of our algorithms. Sections 2 and 3 are summaries of results originally presented in [1, 3]. For the sake of brevity, and because we aim for a self-contained paper, some propositions are only enunciated. Their corresponding proofs and more specific details can be found in [1, 3]. In Section 2, the main concepts and basic algorithms behind the nD-EVM are described, while Section 3 presents an algorithm for extracting forward and backward differences of an nD-OPP.

In [7], Rodríguez and Ayala describe an EVM-based algorithm for connected components labeling. It works specifically for 2D and 3D-OPPs. First, they obtain a particular partitioning from the 3D-EVM known as ordered union of disjoint boxes (OUODB), which is, in fact, a special kind of cell decomposition [7]. Then, once the OUODB partition has been achieved, it follows a process which is based in the two-pass approach. We take into account some ideas presented by Rodríguez and Ayala, but our proposal deals with a higher-dimensional context, that is, with nD-OPPs, and it works directly with their corresponding nD-EVM representations.

Section 5 describes the second contribution of this work: a methodology for extracting kD boundary elements from an nD-OPP represented through the nD-EVM. It is well known that a boundary model for a 3D solid object is a description of the faces, edges, and vertices that compose its boundary together with the information about the connectivity between those elements [15]. However, the boundary representations can be recursively applied not only to solids, surfaces, or segments but to n-dimensional polytopes [16]. For Putnam and Subrahmanyan, a polytope’s boundary representation can be seen as a boundary tree [17]. In the tree, each node is split into a component for each element that it bounds. An element (vertex, edge, etc.) will be represented several times inside the tree, one for each boundary that it belongs to. See Figure 1 for a cube’s boundary tree.

The way we extract kD boundary elements from an nD-OPP represented through the nD-EVM will be reminiscent to the reconstruction of the boundary tree associated with such nD-OPP. Moreover, our methodology is strongly sustained in the use of our proposed connected components labeling algorithm (Section 4) and the procedures described in Sections 2 and 3. Some study cases will be presented in order to appreciate the information our proposed procedure can share. Finally, in Section 6, we determine, in empirical way, the time complexity of the algorithm presented in Section 5 in order to provide evidence of its efficiency specifically when higher-dimensional nD-OPPs are considered.

2. The Extreme Vertices Model in the n-Dimensional Space (nD-EVM)

In Section 2.1, some conventions and preliminary background related directly with orthogonal polytopes will be introduced. In Section 2.2, the foundations of the nD-EVM will be established. Section 2.3 presents some basic algorithms under the EVM.

3. Forward and Backward Differences of an nD-OPP

One interesting characteristic, described in [1], of forward and backward differences of a 3D-OPP, is that forward differences are the sets of faces, on a couplet, whose normal vectors point to the positive side of the coordinate axis perpendicular to such couplet. Similarly, backward differences are the sets of faces, on a couplet, whose normal vectors point to the negative side of the coordinate axis perpendicular to such couplet. By this way, it is provided a procedure for obtaining the correct orientation of faces in a 3D-OPP when it is converted from 3D-EVM to a boundary representation.

In the context of an nD-OPP p, there are methods to identify normal vectors in the (n − 1)D cells included in p’s boundary. For example, simplicial combinatorial topology provides methodologies assuming a polytope is represented under a simplexation. Such methods operate under the fact the n + 1 vertices of an nD simplex are labeled and sorted. Such sorting corresponds to an odd or an even permutation. By taking n vertices from the n + 1 vertices of the nD simplex, we get the vertices corresponding to one of its (n − 1)D-cells. In this point, usually, a set of entirely arbitrary rules are given to determine the normal vector to such (n − 1)D cells; see for example, [19, 20]. Such rules establish, according to the parity of the permutation, if the assigned normal vector points towards the interior of the polytope or outside of it.

On the other hand, there are works that consider the determination of normal vectors by taking into account properties of the cross product and the vectors that compose the basis of nD space. For example, Kolcun [21] provides one of such methodologies; however, it is also dependent of polytopes are represented through a simplexation. In this last sense, forward and backward differences will provide us a powerful tool, because, in fact, given an nD-OPP p, forward differences $$ are the sets of (n − 1)D cells lying on $$, whose normal vectors point to the positive side of the coordinate axis X_i, while backward differences $$ are the sets of (n − 1)D cells also lying on $$ but whose normal vectors point to the negative side of the coordinate X_i-axis.

Figure 2 shows a 3D-OPP and its corresponding sets of 2D-couplets perpendicular to X₁, X₂, and X₃-axes (Figures 2(b), 2(c), 2(d)). According to Figure 2(a), the OPP has 5 non-extreme vertices which are marked in white. Three of them have four coplanar incident odd edges; another one has six incident odd edges, and the last one has exactly two incident collinear odd edges. The remaining vertices, actually the extreme vertices, have exactly three linearly independent odd edges. Table 1 shows the extraction, for the 3D-OPP shown in Figure 2(a), of its faces and their correct orientation through forward and backward differences. The first row shows sections perpendicular to X₁-axis. Through them, we compute forward differences $$ to $$ in order to obtain the faces whose normal vector points towards the positive side of X₁-axis. On the other hand, these same sections share us to compute backward differences $$ to $$, which are composed by the set of faces whose normal vector points towards the negative side of X₁-axis. In a similar way, the remaining two rows of Table 1 show sections perpendicular to X₂ and X₃-axes and their respective forward and backward differences.

Table 1. Forward and backward differences of a 3D-OPP (see text for details).

Sections	Forward differences	Backward differences

An algorithm for computing forward and backward differences consists of obtaining projections of sections of the input polytope and processing them through BooleanOperation algorithm by computing regularized difference between two consecutive sections. Algorithm 2 implements these simple ideas in order to compute the forward and backward differences in an nD-OPP p represented through the nD-EVM. Its output will consist of two sets: the first set FD contains the (n − 1)D-EVMs corresponding to forward differences in p, while the second set BD contains the (n − 1)D-EVMs corresponding to backward differences in p. Algorithm 2 will be useful when we describe our procedure for extracting kD boundary elements of an nD-OPP which is represented through the nD-EVM. Such procedure will be described in Section 5.

4. A Connected Components Labeling Algorithm under the nD-EVM

The idea behind the proposed methodology considers to process sequentially each (n − 1)D section of p. Let S_j be the current processed section of p. We obtain, via a recursive call, its (n − 1)D components. Let S_i be the section before S_j. For each (n − 1)D component cS_j in S_j and for each (n − 1)D component cS_i in S_i, it is performed their regularized intersection cS_j∩^*cS_i. According to the result, one of three cases can arise.

Tables 2 and 3 show an example where the above ideas are applied on a 2D-OPP. Such OPP is composed of 22 extreme vertices and has five internal sections which are perpendicular to X₁-axis. Once all sections are processed, it is determined the existence of two components.

Table 2. Connected component labeling over a 2D-OPP (Part 1).

	The projection of section $$ has the 1D component $$. Because $$ is an empty section. Then, Case 3: $$ belongs to the new component 0.
	The projection of section $$ has four 1D components: $$, $$, $$, and $$.
	$$, and $$ does not belong to any component of p. Then, Case 1: $$ now belongs to component 0 (the component which $$ belongs).
	$$, and $$ does not belong to any component of p. Then, Case 1: $$ now belongs to component 0.
	$$. Case 3: $$ belongs to new component 1.
	$$. Case 3: $$ belongs to new component 2.

Table 3. Connected component labeling over a 2D-OPP (Part 2).

	Projection of section $$ has two 1D components: $$ and $$.
	$$, and $$ does not belong to any component of p. Then, Case 1: $$ now belongs to component 0.
	$$, and $$ is associated to component 0. Then, Case 2: $$ also belongs to component 0. No action takes place.
	$$, and $$ belongs to component 0. Case 2: $$ is associated to component 1. Therefore, components 0 and 1 are united in the new component 3.
	$$, and $$ does not belong to any component of p. Case 1: $$ is now associated to component 2.
	The projection of section $$ is composed by segment $$.
	$$, and $$ does not belong to any component of p. Therefore, Case 1: $$ now belongs to component 2.
	The projection of section $$ is composed by segment $$.
	$$, and $$ does not belong to any component of p. Then, Case 1: $$ is now associated to component 2.

A more specific implementation of our procedure is given in Algorithm 3. In order to distinguish between Cases 1 and 2, the algorithm uses a Boolean flag (withoutComponent). When Case 1 is achieved, then cS_j, the current component of section S_j, is already associated to a component of p. Therefore, the flag’s value is inverted for indicating this last property and, for instance, sharing that only Case 2 could be reached in the subsequent iterations. If for all components of S_i, the section before S_j, the intersection with cS_j was empty, then the flag never changed its original value. In this way, Case 3 can be identified.

When the algorithm finishes the processing of sections, each list in componentsP is a list of (n − 1)D sections or a NULL element. If a NULL element is found, then it must be removed. Otherwise, we obtain the corresponding nD-EVM, which at its time corresponds to a component of the input nD-OPP p. It is possible the (n − 1)D sections contained in a given list are not correctly ordered. With the purpose of determining the correct sequence, in Algorithm 3, when a (n − 1)D-OPP is appended, the common X_A coordinates of the previous and next couplets are also introduced with it.

Previously, we mentioned hypercubes C₅ and C₆ shared a 3D volume. When computing regularized intersection between $$ and $$ (their corresponding sections in q) the result was the empty set. This is due to the use of regularized boolean operations: operations between nD polytopes must be dimensionally homogeneous; that is, they must produce as result another nD polytope or the null object [22]. Hypercubes C₅ and C₄ shared a (1D) edge, but the regularized intersection between their corresponding sections, in q, $$ and $$, also produced a null object. A distinct situation arises when the regularized intersection between $$ and $$ is analyzed: Algorithm 3 determined that they are associated with the same component.

The above example has illustrated a property of Algorithm 3. When the foundations behind our method were established, it was commented the algorithm process, not in an explicit way, consecutive slices of the input polytope p. Each nD slice of p has its corresponding representative (n − 1)D section for which Algorithm 3 determines its corresponding (n − 1)D components. Let c₁ and c₂ be nonempty (n − 1)D components such that c₁ is associated to (n − 1)D section $$, while c₂ is associated to (n − 1)D section $$. The fact that c₁ and c₂ have empty regularized intersection implies (1) that their corresponding nD regions are disjoint and, therefore, they have null adjacencies, or (2) that some parts of its corresponding slices have a kD adjacency; that is, some kD elements, k = 0,1, 2, …, n − 2, are, completely or partially, shared. In both cases, Algorithm 3 uses this kind of adjacencies, via the result of regularized intersection between c₁ and c₂, for determining that the corresponding nD regions are disjoint and, for instance, associate them with different components. Hence, a nD component shared by Algorithm 3 corresponds to those parts of the input nD-OPP that are united via (n − 1)D adjacencies. The way Algorithm 3 breaks a polytope will be very useful in the following sections, specifically when we present our methodology for identifying kD boundary elements.

5. Extracting kD Boundary Elements from an nD-OPP

This section presents the second main contribution of this work. As commented in Section 1, the way we extract kD boundary elements from an nD-OPP represented through the nD-EVM will be reminiscent to the reconstruction of the boundary tree associated to such nD-OPP. According to Section 3, forward and backward differences can be computed through Algorithm 2. In fact, all $$ and $$ from an nD-OPP are (n − 1)D-OPPs embedded in (n − 1)D space, because the projection operator is used in their corresponding definitions: $$ and $$. If such forward and backward differences were computed through our proposed algorithm, then they are expressed as $$ and $$. If we apply again Algorithm 2 to such (n − 1)D-OPPs, we will get new forward and backward differences that correspond to the (n − 2)D oriented cells on the boundary of such (n − 1)D-OPPs. These new forward and backward differences are themselves (n − 2)D-OPPs represented through the EVM. Hence, by applying again Algorithm 2 to them, we obtain their associated (n − 3)D oriented cells grouped as forward and backward differences. This procedure generates a recursive process which descends in the number of dimensions. In each recursivity level, we obtain forward and backward differences associated to the input kD-OPPs, 1 ≤ k ≤ n. The base case is reached when n = 1. In this situation, the boundary of a 1D-OPP is described by the beginning and ending extreme vertices of each one of its composing segments.

Algorithm 4 implements the above-proposed ideas in order to identify and to extract kD boundary elements from a nD-OPP. Input parameters for our algorithm require the EVM associated with the input nD-OPP p, the number k of dimensions, and a list, where the boundary elements of p are going to be stored. Such a list, called boundaryElements, is assumed to be a list of lists such that boundaryElements( k) returns the list that contains the identified kD elements, k = 0,1, 2, …, n − 1. When k = n, then we have the main call with nD-OPP p, n ≥ 2, and list boundaryElements initialized with n empty lists (if n = 1, then the boundary elements of p are precisely its extreme vertices which can be directly extracted from the EVM₁(p)). When 2 ≤ k < n, then the input OPP is, in fact, a kD boundary element of p and boundaryElements contains the elements (vertices, edges, faces, etc.) discovered prior to such recursive call. In the algorithm’s basic case, when k = 1, no action is performed, because the input 1D-OPP has only as boundary elements the vertices that bound its corresponding segment. The vertices in such 1D-OPP have been previously identified, because the algorithm always receives and uses a list of discovered vertices. Such a list is located in the input boundaryElements at position zero, and it is updated, as required, along main and all recursive calls.

Consider the 3D-OPP p shown in Figure 5. Suppose that the ordering of the coordinates of 3D-EVM of p is X₁X₂X₃. All the vertices of p are extreme except that with a dotted circle, because it has five incident edges and four of them are odd edges, while the fifth one, which is parallel to X₃-axis, is, in fact, an even edge; hence, it does not belong to any brink of p. There are another two even edges in p: one of them is parallel to X₁-axis while the other to X₂-axis. Tables 4 and 5 show the way Algorithm 4 discovers faces, perpendicular to X₁-axis, and vertices of p (we recall that our algorithm lists boundary elements’ vertices in the order they are discovered). Table 4 corresponds to the processing of forward differences. $$ is composed by only one component and its 2D-EVM shares the discovering of four vertices. Three of them correspond to projections of extreme vertices of p, because they have only 2 coordinates, while the fourth one precisely corresponds to the projection of the nonextreme vertex indicated in Figure 5. The vertices are completed, in order to have three coordinates, by annexing them the common coordinate of its corresponding forward difference $$. By this way, vertices v₁, v₂, v₃, and v₄, and the face they define, are initially discovered. Via Algorithm 3, $$ is separated in two components. Each component corresponds to a new face defined by four vertices. Both faces and the eight vertices are, respectively, added to the lists of discovered faces and vertices.

Table 4. Identifying faces, of the 3D-OPP from Figure 5, through forward differences and Algorithm 4 (see text for details. Faces’ vertices are listed in the order they are discovered).

	Forward difference	Connected components labeling	Discovered vertices and faces
			v1,   v2,   v3,   v4
			(Vertex v1 was not in EVM3(p)). V(p) = {v1, v2, v3, v4} F(p) = {{v1, v2, v3, v4}}
			v5, v6, v7, v8 V(p) = {v1, v2, v3,   v4, v5, v6, v7, v8} F(p) = {{v1, v2, v3, v4},   {v5, v6, v7, v8}}
			v9, v10, v11, v12 V(p) = {v1, v2, v3, v4,   v5, v6, v7, v8, v9, v10,      v11, v12} F(p) = {{v1, v2, v3, v4},   {v5, v6, v7, v8},      {v9, v10, v11, v12}}
			v13, v14, v15, v16 V(p) = {v1, v2, v3, v4, v5, v6, v7, v8, v9, v10,      v11, v12, v13, v14,   v15, v16} F(p) = {{v1,   v2,   v3,   v4},      {v5, v6, v7, v8},   {v9, v10, v11, v12},         {v13,   v14,   v15,   v16}}
			v17, v18, v19, v20 V(p) = {v1, v2, v3, v4, v5, v6, v7, v8, v9, v10,      v11, v12, v13, v14, v15, v16, v17, v18,      v19, v20} F(p) = {{v1, v2, v3, v4}, {v5, v6, v7, v8},      {v9, v10, v11, v12}, {v13, v14, v15, v16},       {v17, v18, v19, v20}}

Table 5. Identifying faces, of the 3D-OPP from Figure 5, through backward differences and Algorithm 4 (see text for details. Faces’ vertices are listed in the order they are discovered).

	Backward difference	Connected components labeling	Discovered vertices and faces
			v21, v22, v23, v24 V(p) = {v1, v2, v3, v4, v5, v6, v7, v8, v9,      v10, v11, v12, v13, v14, v15, v16,       v17, v18, v19, v20, v21, v22, v23, v24} F(p) = {{v1, v2, v3, v4}, {v5, v6, v7, v8}, {v9, v10, v11, v12}, {v13, v14, v15, v16}, {v17, v18, v19, v20}, {v21, v22, v23, v24}}
			v2, v25, v26, v27 (Vertex v2 was discovered when processing $$) V(p) = {v1, v2, v3, v4, v5, v6, v7, v8, v9,       v10, v11, v12, v13, v14, v15, v16,       v17, v18, v19, v20, v21, v22, v23, v24,       v25, v26, v27} F(p) = {{v1, v2, v3, v4}, {v5, v6, v7, v8}, {v9, v10, v11, v12}, {v13, v14, v15, v16}, {v17, v18, v19, v20}, {v21, v22, v23, v24}, {v2, v25, v26, v27}}
			v1, v2, v28, v29 (Vertices v1 and v2 were discovered when processing $$) V(p) = {v1, v2, v3, v4, v5, v6, v7, v8, v9,       v10, v11, v12, v13, v14, v15, v16, v17,       v18, v19, v20, v21, v22, v23, v24, v25,      v26, v27, v28, v29}   F(p) = {{v1, v2, v3, v4},   {v5, v6, v7, v8},   {v9, v10, v11, v12},   {v13, v14, v15, v16},   {v17, v18, v19, v20},   {v21, v22, v23, v24},   {v2, v25, v26, v27},   {v1, v2, v28, v29}}

Table 5 shows the processing of backward differences. $$ corresponds to a 2D-OPP in which six of its seven vertices are extreme vertices. When applying Algorithm 3 over $$, we obtained two components. The extreme vertices of $$ are present in the components, but a new vertex appear which is product of the separation of the original face. Such a vertex (v₂), in fact, was previously identified when processing $$ (Table 4). nonextreme vertex v₁ is present in the second component: it was also identified when $$ was processed. The remaining vertices in both components, and the faces they define, are appended to their corresponding lists.

Each one of the 2D components in the forward and backward differences of p is used as input for the recursive calls of Algorithm 4. These calls have the objective of identifying edges perpendicular to X₂-axis. Table 6 presents the way Algorithm 4 discovers of some of these edges. When $$ is sent as input its corresponding 1D forward and backward differences, perpendicular to X₂-axis, are computed. Two edges are identified: one is defined by vertices v₃ and v₄ (an odd edge), while the other is defined by vertices v₁ and v₂. Edge {v₁, v₂} is one of the three even edges that 3D-OPP p has. According to previous sections, nonextreme vertices are ignored by the EVM. Moreover, when brinks are obtained from an EVM, even edges remain unidentified, because they are not part of brinks. Tables 4 and 6 exemplify situations where these types of former boundary elements are obtained after computing forward and backward differences.

Table 6. Identifying some edges, of the 3D-OPP from Figure 5, through Algorithm 4 (see text for details).

	Input 2D-OPP	1D Forward and backward differences	Connected components labeling	Discovered edges
				{v3, v4}   E(p) = {{v3, v4}}
				{v1, v2} (even edge)   E(p) = {{v3, v4}, {v1, v2}}
				{v7, v8}   E(p) = {{v3, v4},   {v1, v2}, {v7, v8}}
				{v5, v6}   E(p) = {{v3, v4}, {v1, v2},   {v7, v8},   {v5, v6}}
				{v11, v12} E(p) = {{v3, v4}, {v1, v2}, {v7, v8}, {v5, v6}, {v11, v12}}
				{v9, v10}   E(p) = {{v3, v4}, {v1, v2},   {v7, v8}, {v5, v6}, {v11, v12}, {v9, v10}}

When considering nD orthogonal polytopes, n ≥ 4, Algorithm 4 is clearly capable of identifying nonextreme vertices and even edges. Furthermore, it is capable of discovering those kD boundary elements that cannot be described via brinks. Consider the 4D-OPP p presented in Figure 6(a). Such polytope can be seen as two hypercubes sharing a face (which is shaded in gray). The face is composed by four nonextreme vertices and four even edges. When p’s brinks, parallel to X₁ to X₄-axes, are obtained (Figure 6(b)), the shared face’s elements are not present, because the 4D-EVM only stores extreme vertices which in time define brinks which are formed only by odd edges. Figure 6(c) presents the three 3D couplets, perpendicular to X₁-axis, of p. Each couplet is formed by a volume. The three volumes appear to intersect, but this is an effect of the 4D-3D-2D projections used. Figure 6(d) presents p’s two 3D forward differences perpendicular to X₁-axis. When processing $$, Algorithm 4 detects a 3D boundary volume defined by eight vertices: four of them correspond to extreme vertices of p, while the other four correspond to the vertices of the shared face: such vertices did not belong to EVM₄(p). These four vertices are detected again when processing backward difference $$ (see Figure 6(e)). Three-dimensional forward difference $$ is used, in a recursive call, as input for Algorithm 4 (see Figure 6(f)). When its 2D forward and backward differences, perpendicular to X₄-axis, are processed and specifically when processing its only backward difference, the shared face is formerly discovered and stored in the list of p’s boundary faces. The edges of such face are formerly discovered when this face is then sent as input, in a new recursive call, of Algorithm 4.

We conclude this section by mentioning that it is important to take into account the coordinates ordering in an EVM determines which boundary elements are identified. Suppose that we use the sorting X₁X₄X₂X₃. Algorithm 2 will extract forward and backward differences perpendicular to X₁-axis. Then, in turn, Algorithm 4 shares to identify 3D boundary volumes perpendicular precisely to X₁-axis (see Figures 6(d) and 6(e)). When each one of these volumes is sent as input in the corresponding recursive calls, we have input 3D-EVMs sorted as X₄X₂X₃. Hence, there are identified, again, because of the use of Algorithm 2, faces perpendicular to X₄-axis. In this phase, we are working with volumes embedded in a 3D space, because of the use of projection operator which has removed the X₁-coordinate. But, when the source 4D Space is taken into account, it can be determined, in fact, such faces are perpendicular to the plane described by X₁ and X₄ axes, because they precisely belong to volumes perpendicular to X₁-axis (see Figure 6(f)). When each face, expressed as a 2D-EVM, is sent again as input, we identify edges perpendicular to X₂-axis, formally, edges perpendicular to the 3D hyperplane described by X₁, X₄, and X₂ axes. Some applications could require to have access to boundary elements which cannot be identified via a given coordinates ordering. In this sense, a new sorting of the corresponding EVM is required, but it can be achieved in efficient time respect to the number of extreme vertices in the corresponding EVM. By this way, for example, coordinates sorting X₃X₄X₁X₂ will share to identify 3D volumes perpendicular to X₃-axis, faces perpendicular to the plane X₃X₄, and edges perpendicular to the 3D hyperplane X₃X₄X₁.

6. An Experimental Time Complexity Analysis for Boundary Extraction under the nD-EVM

Table 7 shows some statistics related to our generated polytopes. In Figure 7 the behavior of Algorithm 4 with our testing sets of nD-OPPs can be visualized. In the same chart the corresponding trendline for each value of n whose associated equations are shown in Table 8 can be also appreciated.

We can then observe in the obtained trendlines (Table 8) that the exponents associated with the number of vertices vary between 1 and 1.5. These experimentally identified complexities for our Algorithm 4 provide us elements to determine its temporal efficiency when we extract boundary elements from an nD-OPP expressed as an EVM.

7. Concluding Remarks and Future Work

In this work, we have provided two contributions: an algorithm for computing connected components labeling and an algorithm for extracting boundary elements. The procedures deal with the dominion of the n-dimensional orthogonal pseudo-polytopes, and they are specified in terms of the extreme vertices model in the n-dimensional space. As seen before, both algorithms are sustained in the basic methodologies provided by the nD-EVM. As commented in Section 2, some of such basic algorithms in time are sustained in the MergeXor algorithm. It computes the regularized XOR between two nD-OPPs expressed in the EVM but in terms of the ordinary XOR operation. This implies MergeXor, as its name indicates, is implemented as a merging procedure that only takes in account those extreme vertices present in the first or second input EVMs but not in both. Therefore, it can be specified as a merging-like procedure with an execution linear time given by the sum of the cardinalities of the input EVMs [1]. On one hand, this has as a consequence the temporal efficiency of the basic EVM algorithms. On the other hand, as seen in Section 6 and from an empirical point of view, we have elements to sustain the efficiency of the algorithms provided here.

As part of our future work, and particularly, immediate applications for Algorithms 3 and 4, we comment that we will attack the problem related to the automatic classification of video sequences. In [23], we describe a methodology for representing 2D color video sequences as 4D-OPPs embedded in a 4D color-space-time geometry. Our idea is the use of geometrical and topological properties, such as boundary descriptions, connected components, and discrete compactness, in order to determine similarities and differences between sequences and for instance to classify them. In [5], part of this work has been boarded using only discrete compactness, and the obtained results are promising. We are going to incorporate the information provided by Algorithms 3 and 4 in order to determine if they can contribute to enhance the results.