# Computing the Discrete Compactness  of Orthogonal Pseudo-Polytopes via TheirnD-EVM Representation

Authors: Ricardo Pérez-Aguila
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

This work is devoted to present a methodology for the computation of Discrete Compactness inn-dimensional orthogonal pseudo-polytopes. The proposed procedures take in account compactness' definitions originally presented for the 2D and 3D cases and extend them directly for considering the nD case. There are introduced efficient algorithms for computing discrete compactness which are based on an orthogonal polytopes representation scheme known as the Extreme Vertices Model in the n-Dimensional Space (nD-EVM). It will be shown the potential of the application of Discrete Compactness in higher-dimensional contexts by applying it, through EVM-based algorithms, in the classification of video sequences, associated to the monitoring of a volcano's activity, which are expressed as 4D orthogonal polytopes in the space-color-time geometry.


---

## Body

## 1. Introduction

In areas such as image processing, pattern recognition, and computer vision, there is required to characterize for a given object its topological and geometrical factors. They have a paramount role in more elaborated tasks such as those related to classification, indexing, or comparison. Some of these factors describe the shape of an object. One of them, and one of the most used, is the shape compactness [1]. The shape compactness of an object refers to a measure between the object and an ideal object [2]. In the 2D euclidean space, shape compactness is usually computed via the well-known ratio(1.1)C=P24πA,
where P is the perimeter of an object and A its area. Such ratio has its origins in the isoperimetric inequality:(1.2)P2≥4πA.
It is actually the solution to the isoperimetric problem which states the question related to find the simple closed curve that maximizes the area of its enclosed region [3]. The equality is obtained when the considered curve is a circle. Hence, as pointed out in [1], the ratio for shape compactness is in effect comparing an object with a circle. In the 3D space the isoperimetric inequality is given by(1.3)A3≥36πV2,
where A is the area of the boundary of a 3D object while V is its volume. Hence, the ratio(1.4)C=A336πV2
denotes shape compactness of a 3D object, and it effectively is comparing such object with a sphere.As [1, 4] point out, these classical ratios are very sensitive to variations in the shape of an object. Moreover, they point out, when the above definitions are applied to objects defined via pixelizations (in the 2D case) or voxelizations (3D case), that small changes in the final object’s boundary produce more important variations in the computed values. Consider, for example, the sets of boxes presented in Figure 1. The square described by the union of the boxes shown in Figure 1(a) has a perimeter of 32 u while its area is 64 u2. Figure 1(b) shows a polygon that can be seen as a modified version (because of noise, artifacts, digitalization scheme, etc.) of the previous one. Its perimeter is given by 58 u. Both polygons have the same area, but their shapes have some slight differences. Shape compactness for the first polygon is given by 1.2732 while for the second is 4.1827. These values are significantly distinct, and by considering shape compactness as a rule for classification, this could imply that they are very different objects.Polygons defined by the union of 64 unitary boxes.
(a)
Perimeter: 32u, Area: 64 u2(b)
Perimeter: 58u, Area: 64 u2In order to provide a solution to the above problem, Bribiesca, in [1, 5], defined the Discrete Compactness. It has its foundation on the notion of counting the number of edges (in the 2D case) and faces (in the 3D case) which are shared between pixels or voxels, according to the case, that define an object. Discrete Compactness is given by the following expression [1, 5]:(1.5)CD(p)=LC(p)-LCminLCmax-LCmin,where(i)
LC(p) is the number of shared edges (faces) within an object p consisting of m pixels (voxels)(ii)
LCmaxis the the maximum number of shared edges (faces) achieved with an object consisting of m pixels (voxels)(iii)
LCminis the minimum number of shared edges (faces) achieved with an object consisting of m pixels (voxels)(iv)
CD(p)∈[0,1].In [1] there are used, for the 2D case, LCmax=2(m-m) and LCmin=m-1, which, respectively, describe the maximum and minimum number of internal contacts (shared edges) between the m pixels forming a squared object. It is clear, in this case, when CD(p)=1 the object p corresponds to a square of sides m, and when CD(p)=0 it corresponds to a rectangle with base of length 1 and height m. For example, considering again the polygons presented in Figure 1, we have LC=112 for that shown in Figure 1(a), while LC=99 for the polygon in Figure 1(b). In both cases m = 64, hence, LCmax=112 and LCmin=63. Then, discrete compactness for the polygon in Figure 1(a) is given by CD=1 while the other has CD=0.7346. In [4] it is established that LCmin=0. Hence, if CD(p)=0, then the object corresponds to a chain of pixels such that no edges, and only vertices, are shared. By considering LCmin=0 then discrete compactness for the polygons in Figures 1(a) and 1(b) are 1 and 0.8839, respectively. It both cases, it is clear that discrete compactness provides us a more robust criterion for objects’ comparison/classification/description of shapes under the advantage it is much less sensitive to variations in their shape. For the 3D case, in [1] it is used LCmax=3(m-m2/3). If m is a power of 3, then the given LCmax provides the number of shared faces in an array of voxels that correspond to a cube of edges of length m3. By using LCmin=m-1 then it is defined a stack of m voxels [1].


## 2. Problem Statement

Ann-dimensional Euclidean polytope Πn is defined as a finite region of n-dimensional Euclidean space enclosed by a finite number of (n-1)-dimensional hyperplanes [6]. The finiteness of the region implies that the number Nn-1 of bounding hyperplanes satisfies the inequality Nn-1>n. The part of the polytope that lies on one of these hyperplanes is called a cell. Each cell of a Πn is an (n-1)-Dimensional polytope, Πn-1. The cells of a Πn-1 are Πn-2's, and so on; thus it is obtained a descending sequence of elements Πn-3, Πn-4,…, Π3 (a volume), Π2 (a polygon), Π1 (an edge), Π0 (a vertex).The representation of a polytope through a scheme of hyperspatial occupancy enumeration is essentially a list of identical hyperspatial cells occupied by the polytope. Specific types of cells, called hypervoxels [7], are hyper-boxes (hypercubes, for example) of a fixed size that lie in a fixed grid in the n-dimensional Space. By instantiation, it is well known that a 2D hypervoxel is a pixel while a 3D hypervoxel is a voxel; the term rexel is suggested for referencing a 4D hypervoxel [7]. The collection of hyperboxes can be codified as an n-Dimensional array Cx1,x2,…,xn. The array will represent the coloration of each hypervoxel. If Cx1,x2,…,xn=0, the white hypervoxel Cx1,x2,…,xn represents an unoccupied region from the n-Dimensional space. If Cx1,x2,…,xn=1, then the black hypervoxel Cx1,x2,…,xn represents a used region from the n-Dimensional space. Hence, the set of black cells defines a polytope whose vertices coincide with some of the occupied cells’ vertices.It is clear that Bribiesca’s definition of Discrete Compactness can be extended for consideringn-Dimensional polytopes, and in the particular dominion of this work, n-Dimensional Orthogonal Pseudo-Polytopes (nD-OPPs). We will consider those nD-OPPs that can be seen as the result of a hypervoxelization such that hypervoxels are unit nD hypercubes with integer coordinates. It is well known that an nD hypercube has 2n boundary (n-1)D cells [8]: 2 vertices in a segment, 4 edges in a square, 6 faces in a cube, 8 volumes in a 4D hypercube, and so on. Hence, LC(p) denotes the number of shared (n-1)D cells within polytope p consisting of m hypervoxels while LCmax and LCmin correspond, respectively, to the maximum and minimum number of shared (n-1)D cells achieved with objects composed by m hypervoxels.When using hypervoxelizations for representing and manipulatingnD polytopes some compromises should be taken in account. In particular is the one related to the representation’s spatial complexity. It is well known that spatial complexity of a hypervoxelization is at least(2.1)∏i=1nmi,
where mi,1≤i≤n, is the length of the grid along Xi-axis. For example, a 4D grid with m1 = m2 = m3 = m4 = 1,000 is required to store 1 trillion (1×1012) hypervoxels. For that reason, in this work we will concentrate on expressing nD-OPPs via a polytopes’ concise representation scheme known as the Extreme Vertices Model in the n-Dimensional Space (nD-EVM). The EVM is a model originally established by Aguilera and Ayala in [9, 10] for representing 1D, 2D, and 3D-OPPs. In [11], EVM’s properties in the n-Dimensional Euclidean Space were formally proved, leading to characterize it as a complete representation scheme for nD-OPPs. In [10, 11] there are described efficient algorithms for performing some of the most used operations in solid and polytopes modeling such as regularized boolean operations, set membership classification, and measure queries. The conciseness of the EVM lies in the fact it only stores some specific vertices of a polytope: the Extreme Vertices. Via such subset of the polytope’s vertices, it is possible to obtain much geometrical and topological information about the polytope and to perform operations as the ones previously mentioned. Now, returning to the question related to hypervoxelizations’ complexity, we commented before that in a hypervoxelization the set of black hypervoxels defines a polytope, actually an nD-OPP. The hypervoxels in such set can be seen as a set of quasidisjoint nD-OPPs. Based on this observation, we will describe a straight methodology for converting a hypervoxelization to a concise EVM representation. In Section 3 we will describe formally to nD-OPPs (Section 3.1), and we will present a summary of the foundations behind the nD-EVM (Section 3.2). Section 3.3 presents basic algorithms under the nD-EVM while Section 3.4 deals with two algorithms for interrogating and manipulating nD-OPPs represented via the nD-EVM: the first one computes the nD content of an OPP while the second corresponds to computation of regularized boolean operations between OPPs. Finally, Section 3.5 presents the procedure for hypervoxelizations to nD-EVM conversion.The main contribution of this work is the specification of efficient procedures that provide us a way to infer the number of hypervoxels that originally composed annD-OPP. In this sense, we assume that such OPP fits exactly in a hypervoxelization, where hypervoxels are unit nD hypercubes whose vertices have integer coordinates. More specifically, given an EVM we will determine the number of internals contacts, that is, the number of shared (n-1)D cells, that took place between the hypervoxels that originally defined the polytope. By this way, we will present in Section 4 an EVM-based algorithm for determining LC(p) for a given nD-OPP p. Such algorithm will lead to the specification of a procedure for computing the Discrete Compactness of an nD-OPP. After that, in Section 5, it will be described a methodology, originally presented in [11, 12], for representing and manipulating color 2D animations via EVM-modeled polytopes embedded in 4D space-color-time geometry. Then, in Section 6, we will describe an application of our proposed EVM-based algorithms for computing Discrete Compactness. Specifically, we present an application oriented to classification of image sequences which correspond to a volcano’s activity. It will be seen how the obtained results provide experimental evidence about the applicability of Discrete Compactness in higher dimensional contexts.


## 3. The Extreme Vertices Model in then-Dimensional Space (nD-EVM)

This section is a summary of results originally presented in [10, 11]. For the sake of brevity, some propositions are only enunciated. Their corresponding proofs can be found in the two aforementioned references.


### 3.1. The n-Dimensional Orthogonal Pseudo-Polytopes (nD-OPPs)

Definition 3.1 (see [13]).
ASingular n-dimensional hyper-box in ℝn is given by the continuous function
(3.1)In:[0,1]n→[0,1]n,x~In(x)=x.
A general singular k-dimensional hyper-box in the closed set A⊂ℝn is the continuous function
(3.2)c:[0,1]k→A.Definition 3.2 (see [13]).
For alli,1≤i≤n,the two singular(n-1)D hyper-boxes I(i,0)n and I(i,1)n are defined as follows. If x∈[0,1]n-1, then I(i,0)n(x)=(x1,…,xi-1,0,xi,…,xn-1) and I(i,1)n(x)=(x1,…,xi-1,1,xi,…,xn-1).Definition 3.3 (see [13]).
Theorientationof an (n-1)D cell c∘I(i,α)n is given by(-1)α+i. It is said cell c∘I(i,α)n is oriented when it is expressed by the scalar-function product (-1)i+α·c∘I(i,α)n.Definition 3.4 (see [13]).
A formal linear combination of general singularkD hyper-boxes,1 ≤k≤n, for a closed setAis called ak-chain.Definition 3.5 (see [13]).
Theboundary of an n-chain∑cj, where each cj is a general singular nD hyper-box, is given by
(3.3)∂(∑cj)=∑∂(cj)=∑(∑i=1n(∑α=0,1(-1)i+α·cj∘I(i,α)n)).Definition 3.6.
A collectionc1, c2, …, ck,1 ≤k≤ 2n, of general singular nD hyper-boxes is acombination ofnD hyper-boxesif and only if
(3.4)[⋂α=1kcα([0,1]n)=(0,…,0︸n)]∧[(∀i,j,i≠j,1≤i,j≤k)(ci([0,1]n)≠cj([0,1]n))].In the above definition the first part of the conjunction establishes that the intersection between all thenD general singular hyper-boxes is the origin, while the second part establishes that there are not overlapping nD hyper-boxes.Definition 3.7.
Ann-dimensional orthogonal pseudo-polytopep, or just an nD-OPPp, is an n-chain composed by nD hyper-boxes arranged in such way that by selecting a vertex, in any of these hyper-boxes, it describes a combination of nD hyper-boxes (Definition 3.6) composed up to 2n hyper-boxes.


### 3.2.nD-EVM’s Fundamentals

Definition 3.8.
Letcbe a combination of hyper-boxes in the n-Dimensional space. An Odd Adjacency Edgeofc, or just anOdd Edge, is an edge with an odd number of incident hyper-boxes of c.Conversely, if an edge has an even number of incident hyper-boxes of c, it is called Even Adjacency Edge, or just Even Edge.Definition 3.9.
Abrinkorextended edge is the maximal uninterrupted segment, built out of a sequence of collinear and contiguous odd edges of an nD-OPP.From the above definition, every even edge of annD-OPP does not belong to brinks. On the other hand, every brink consists of m odd edges,m≥ 1, and contains m+ 1 vertices. Two of these vertices are at either extreme of the brink and the remaining m-1 are interior vertices.Definition 3.10.
The ending vertices of all the brinks inp will be called Extreme Vertices of an nD-OPP p.  EV(p)will denote to the set of Extreme Vertices of p.Property 3.11.
Any extreme vertex of an n D-OPP, n≥ 1, when is locally described by a set of surrounding n D hyper-boxes, has exactly n incident linearly independent odd edges.Figure2 shows an example of a 3D-OPP p. Vertices v1 and v2 are nonextreme vertices because, in the case of v1, it has six incident odd edges, while vertex v2 has four incident coplanar odd edges (see Property 3.11). In the figure can be also appreciated that exactly three linearly independent odd edges are incident to the remaining vertices, actually, the Extreme Vertices of p.Figure 2
Example of a 3D-OPP and its set of Extreme Vertices (Continuous lines indicate odd edges, dotted lines indicate even edges, black points correspond to extreme vertices, and white points correspond to non extreme vertices).The brinks in annD-OPP p can be classified according to the main axis to which they are parallel. Since the extreme vertices mark the end of brinks in the n orthogonal directions, is that any of the n possible sets of brinks parallel to Xi-axis, 1 ≤i≤n, produce to the same set EV(p). See in Figure 3(a) the brinks parallel to X2-axis for the 3D-OPP originally presented in Figure 2.Illustrating some EVM concepts over a 3D-OPP (See text for details).
(a)(b)(c)(d)(e)(f)Definition 3.12.
Letp be an nD-OPP. A kD extended hypervolume of p, 1 <k<n, denoted by ϕ(p), is the maximal set of kD cells of p that lies in a kD space, such that a kD cell e0 belongs to a kD extended hypervolume if and only if e0 belongs to an (n-1)D cell present in ∂(p) (see Definition 3.5), that is,
(3.5)(e0∈ϕ(p))⇔(∃c,cbelongsto∂(p))(e0([0,1]k)⊆c([0,1]n-1)).Definition 3.13.
Letp be an nD-OPP. The Extreme Vertices Model of p, denoted by EVMn(p), is defined as the model as only stores to all the extreme vertices of p.Let Q be a finite set of points inℝ3. In [10] was defined the ABC-sorted set of Q as the set resulting from sorting Q according to coordinate A, then to coordinate B, and then to coordinate C. For instance, a set Q can be ABC-sorted in six different ways. Now, let p be a 3D-OPP. According to [10] the Extreme Vertices Model of p, EVM3(p), denotes the ABC sorted set of the extreme vertices of p. Then EVM3(p) = EV(p) except by the fact that coordinates of points in EV(p) are not necessarily sorted. In general, it is always assumed that coordinates of extreme vertices in the Extreme Vertices Model of an nD-OPP p, EVMn(p), have a fixed coordinates ordering. Moreover, when an operation requires manipulating two EVMs, it is assumed that both sets have the same coordinates ordering.Definition 3.14.
TheProjection Operator for (n-1)D cells, points, and set of points is, respectively, defined as follows.(i)
Letc(I(i,α)n(x))=(x1,…,xn) be an (n-1)D cell embedded in the nD space. Let πj(c(I(i,α)n(x))) denote the projection of the cell c(I(i,α)n(x)) onto an (n-1)D space embedded in nD space whose supporting hyperplane is perpendicular to Xj-axis
(3.6)πj(c(I(i,α)n(x)))=(x1,…,x̂j,…,xn).(ii)
Letv=(x1,…,xn) a point in ℝn. The projection of that point in the (n-1)D space, denoted by πj(v), is given by:
(3.7)πj(v)=(x1,…,x̂j,…,xn).(iii)
Let Q be a set of points inℝn. The projection of the points in Q, denoted by πj(Q), is defined as the set of points in ℝn-1 such that(3.8)πj(Q)={p∈ℝn-1:p=πj(x),x∈Q⊂ℝn},
In all the cases x̂j is the coordinate corresponding to Xj-axis to be suppressed.Definition 3.15.
Consider annD-OPP p as follows.(i)
Letnpi be the number of distinct coordinates present in the vertices of p along Xi-axis, 1 ≤i≤n.(ii)
LetΦki(p) be the kth (n-1)D extended hypervolume, or just a (n-1)D couplet, of p which is perpendicular to Xi-axis, 1 ≤k≤npi.See in Figure3(b) the set of 2D-couplets perpendicular to X2-axis for the 3D-OPP presented in Figure 2.Definition 3.16.
A slice is the region contained in annD-OPP p between two consecutive couplets of p. Sliceki(p) will denote to the kth slice of p which is bounded by Φki(p)andΦk+1i(p), 1 ≤k<npi.Definition 3.17.
Asection is the (n-1)D-OPP, n> 1, resulting from the intersection between an nD-OPP p and an (n-1)D hyperplane perpendicular to the coordinate axis Xi,n≥i≥ 1, which does not coincide with any (n-1)D-couplet of p. A section will be calledexternalorinternal section of p if it is empty or not, respectively.  Ski(p) will refer to the kth section of p between Φki(p) and Φk+1i(p), 1 ≤k<npi. Moreover, S0i(p) andSnpii(p)  will refer to the empty sections of p before  Φ1i(p)  and after ofΦnpii(p), respectively.Property 3.18.
Letp be an n D-OPP. All the (n -1)D hyperplanes perpendicular to Xi -axis, 1 ≤i ≤n, which intersect to Sliceki(p) give the same section Ski(p).The Figures3(c), 3(d), and 3(e) show the slices for a 3D-OPP (originally presented in Figure 2) according to the supporting planes of its 2D-couplets perpendicular to X2-axis. Figure 3(f) presents its corresponding set of internal sections perpendicular to X2-axis.


#### 3.2.1. A Note about Regularized Boolean Operations

Independently of the scheme we consider for the representation ofnD polytopes, it should be feasible to combine them in order to compose new objects [14]. One of the most common methods to combine polytopes is the set theoretical Boolean operations, as the Union, Difference, Intersection, and Exclusive OR. However, the application of an ordinary set theoretical Boolean operation on two polytopes does not necessarily produce a polytope. For example, the ordinary intersection between two cubes with only a common vertex is a point. Instead of using ordinary set theoretical Boolean operators, the Regularized Boolean Operators [15, 16] will be used. The practical purpose of regularization of polytope models is to make them dimensionally homogeneous [17]. The regularization operation can be defined as Regularized(S) = Closure(Interior(S)) which results in a closed regular set. Each regularized Boolean operator is defined in function of an ordinary operator in the following way:(3.9)Aop*B=Closure(Interior(AopB)).
These operators are defined as the closure of the interior of the corresponding set theoretical Boolean operation [16, 18]. In this way, the regularized operations between polytopes always will generate polytopes or a null object (the empty set) [17].


#### 3.2.2. Computing Couplets from Sections

Theorem 3.19.
The projection of the set of (n -1)D couplets,πi(Φki(p)),  1 ≤i  ≤n, of an nD-OPP p, can be obtained by computing the regularized XOR (⊗*) between the projections of its previous πi(Sk-1i(p)) and next πi(Ski(p)) sections, that is, πi(Φki(p))=πi(Sk-1i(p))⊗*πi(Ski(p)), for all k∈[1,npi].


#### 3.2.3. Computing Sections from Couplets

Theorem 3.20.
The projection of any section,πi(Ski(p)), of an nD-OPPp, can be obtained by computing the regularized XOR between the projection of its previous section, πi(Sk-1i(p)), and the projection of its previous couplet πi(Φki(p)):
(3.10)S0i(p)=∅,πi(Ski(p))=πi(Sk-1i(p))⊗*πi(Φki(p)),∀k∈[1,npi].


#### 3.2.4. The Regularized XOR Operation on thenD-EVM

Theorem 3.21.
Letp and q be two nD-OPPs having EVMn(p) and EVMn(q) as their respective Extreme Vertices Models in nD space, then EVMn(p⊗*q)=EVMn(p)⊗EVMn(q).This result allows expressing formulae for computingnD-OPPs sections from couplets and viceversa by means of their corresponding Extreme Vertices Models. They are obtained by combining Theorem 3.21 with Theorem 3.19 and Theorem 3.21 with Theorem 3.20, respectively.Corollary 3.22.
One has thatEVMn-1(πi(Φki(p)))=EVMn-1(πi(Sk-1i(p)))⊗EVMn-1(πi(Ski(p))).Corollary 3.23.
One has thatEVMn-1(πi(Ski(p)))=EVMn-1(πi(Sk-1i(p)))⊗EVMn-1(πi(Φki(p))).


#### 3.2.5. The Regularized Boolean Operations on thenD-EVM

Corollary 3.24.
Letp and q be two nD-OPPs and r = p op*q, where op* is in {∪*,∩*,-*,⊗*}. Then πi(Ski(r))=πi(Ski(p))op*πi(Ski(q)). Moreover, if all these sections lie in the same (n -1)D hyperplane then Ski(r)=Ski(p)op*Ski(q).Now we present the following.Theorem 3.25.
A regularized Boolean operation, op*, where op*∈{∪*,∩*,-*,⊗*}, over two nD-OPPs p and q, both expressed in the nD-EVM, can be carried out by means of the same op* applied over their own sections, expressed through their Extreme Vertices Models, which are (n-1)D-OPPs.This result leads into a recursive process for computing the Regularized Boolean operations using thenD-EVM, which descends on the number of dimensions [10]. The base or trivial case of the recursion corresponds to the 1D-Boolean operations which can be performed using direct methods. In Section 3.4.2 will be described an algorithm for performing Regularized Boolean operations under the nD-EVM which implements the above results.


### 3.3. Basic Algorithms for thenD-EVM

Now, we introduce some primitive operations which are in fact based on those originally presented in [10]. When an operation requires manipulating two EVMs, it is assumed that both sets have the same coordinates ordering. In the following, XA-axis refers to the nD space’s coordinate axis associated to the first coordinate present in the vertices of EVMn(p). For example, given coordinates ordering X1X2X3, for a 3D-OPP, then XA=X1. (i)
InitEVM( ): returns the empty set.(ii)
PutHvl(EVM hvl, EVM p): appends and (n-1)D couplet hvl, embedded in nD space and perpendicular to XA-axis, to the nD-EVM p.(iii)
ReadHvl(EVM p): extracts and returns the next (n-1)D couplet perpendicular to XA-axis from p.(iv)
EndEVM(EVM p): returns true if the end of p along XA-axis has been reached, otherwise, returns false.(v)
SetCoord(EVM hvl, CoordType coord): sets the XA-coordinate to coord on every vertex of the (n-1)D couplet hvl. For coord = 0, it performs the projection πA(p).CoordType is the chosen type for the vertex coordinates.(vi)
GetCoord(EVM hvl): returns the common XA-coordinate of the (n-1)D couplet hvl.(vii)
GetCoordNextHvl(EVM p): returns the common XA-coordinate of the next available (n-1)D couplet, perpendicular to XA-axis, from p.(viii)
MergeXor(EVM p, EVM q): applies the Exclusive OR operation to the vertices of p and q and returns the resulting EVM.Since the EVM is a sorted model, MergeXor function consists in a simple merging-like algorithm, and therefore, it runs on linear time [10]. Its complexity is given by O(Card(EVMn(p)) + Card(EVMn(q))) because each vertex from EVMn(p) and EVMn(q) needs to be processed just once. Moreover, according to Theorem 3.21, the resulting set corresponds to the regularized XOR operation between p and q.From the above primitive operations, and specifically MergeXor, the following pair of algorithms can be easily derived ([10, 11]).(i)
GetHvl(EVM Si, EVM Sj): implements Corollary 3.22, and returns the projection of the couplet between consecutive sections Si and Sj.(ii)
GetSection(EVM S, EVM hvl): implements Corollary 3.23, and returns the projection of the next section of an nD-OPP whose previous section is S.the Algorithm1 computes the sequence of sections of an nD-OPP p from its nD-EVM using the previous functions [10, 11]. It sequentially reads the projections of the (n-1)D couplets hvl of the polytope p. Then it computes the sequence of sections using function GetSection. Each pair of sections Si and Sj (the previous and next sections about the current hvl) is processed by a generic processing procedure (called Process), which performs the desired actions upon Si and Sj (note that some processes may only need one of such sections).Algorithm 1:Computing the sequence of sections from an nD-OPP p.
Input:AnnD-EVM p.ProcedureEVM_to_SectionSequence(EVM p)EVM hvl// Current couplet.EVM Si, Sj// Previous and next sections about hvl.hvl = InitEVM( )Si = InitEVM( )Sj = InitEVM( )hvl = ReadHvl(p)while(Not(EndEVM(p)))Sj = GetSection(Si, hvl)Process(Si, Sj)Si = Sjhvl = ReadHvl(p)// Read next couplet.end-of-whileend-of-procedure


### 3.4. Interrogating and ManipulatingnD-OPPs Represented via the nD-EVM

#### 3.4.1. Computing the Content of annD-OPP

AnnD hyperprism can be generated by the parallel motion of an (n-1)D polytope; it is bounded by the (n-1)D polytope in its initial and final positions and by several (n-1)D hyperprisms [19]. Consider an nD hyperprism Pn whose base is an (n-1)D polytope Pn-1 of content Cn-1. If hn is the distance between its bases, that is, the height of the hyperprism, then its content is given by [19](3.11)Content(Pn)=Content(Pn-1)·hn=Cn-1·hn.If it is the case where Pn-1 is an (n-1)D hyperprism with height hn-1 generated by the parallel motion of an (n-2)D polytope Pn-2, then Cn-1 is given by the expression Cn-1 = Cn-2·hn-1, where Cn-2 is the content of Pn-2. This last expression yields to rewrite the above equation as(3.12)Content(Pn)=(Content(Pn-2)·hn-1)·hn=(Cn-2·hn-1)·hn.By considering that each (n-k)D hyperprism Pn-k is generated by the parallel motion of an (n-k-1)D hyperprism Pn-k-1, where k = 0, 1, 2, …, n-1, then we have that the content of Pn can be computed according to the formula(3.13)Content(Pn)={h1,n=1,Content(Pn-1)·hn,n>1,
where hn is the height of hyperprism Pn. In the base case, where n = 1, the content of a segment is given directly by its “height”, that is, the distance between its two boundary points.The previous idea is extended in order to compute the content ofnD space enclosed by an nD-OPP. In this case we will consider the partition induced by its slices (Definition 3.16). A slice can be seen as a set of one or more disjoint nD hyperprisms whose (n-1)D base is the slice’s section. As pointed out in [10] the volume of a 3D-OPP p can be computed as the sum of the volumes of its 3D slices, where the volume of a Sliceki(p), is given by the product between the area of its respective section Ski(p) (the 2D base of Sliceki(p)) and the distance between Φki(p) and Φk+1i(p) (the height of the 3D prism Sliceki(p)). Now let q = Ski(p). The area of the 2D-OPP q (see Figure 4 for an example) can be computed as the sum of the areas of its 2D slices, where the area of a Sliceki(q), is given by the product between the length of its respective section Ski(q) (the 1D base of Sliceki(q)) and the distance between Φki(q) and Φk+1i(q) (the height of the “2D prism” Sliceki(p)). Finally let r = Ski(q). In the basic case the length of the 1D-OPP r is computed as the sum of the lengths of its brinks.Figure 4
A 2D-OPPq whose area is being computed (see text for details).Letp be an nD-OPP. The nD space enclosed by p, denoted by Content(n)(p), can be computed as the sum of the contents of its nD slices [11](3.14)Content(n)(p)={Length(p)n=1,∑k=1npi-1Content(n-1)(Ski(p))·dist(Φki(p),Φk+1i(p))n>1.
Algorithm 2 implements the above equation in order to compute the content of nD space enclosed by an nD-OPP p expressed through the nD-EVM [10, 11].Algorithm 2:Computing the content of nD space enclosed by an OPP.
Input:AnnD-EVM p.The number n of dimensions.Output:The content of nD space enclosed by p.ProcedureContent(EVM p, int n)real cont = 0.0// The content of nD space enclosed by p.EVM hvl1, hvl2// Consecutive couplets perpendicular to XA-axis.EVM s// Current section of p.if(n = 1)then returnLength(p)// Base case: p is a 1D-OPP.elses = InitEVM( )hvl1 = ReadHvl(p)while(Not(EndEVM(p)))hvl2 = ReadHvl(p)s = GetSection(s, hvl1)cont = cont + Content(s, n-1) * dist(hvl1, hvl2)hvl1 = hvl2end-of-whilereturncontend-of-elseend-of-procedure


#### 3.4.2. The Boolean Operations Algorithm for thenD-EVM

Letp and q be two nD-OPPs represented through the nD-EVM, and let op* be a regularized Boolean operator in {∪*,∩*,-*,⨂*}. The algorithm, originally presented in [10] and based on Theorem 3.25, computes the resulting nD-OPP r = p op* q. Note that r = p ⊗*q can also be trivially performed using Theorem 3.21 [10]. The idea behind the algorithm is the following.(i)
The sequence of sections fromp and q, perpendicular to XA-axis, is obtained first, based on Theorem 3.20.(ii)
Then, according to Corollary3.24, every section of r can recursively be computed as
(3.15)SkA(r)=SkA(p)op*SkA(q).(iii)
Finally,r can be obtained from its sequence of sections, perpendicular to XA-axis, according to Theorem 3.19.Nevertheless, Algorithm3 does not work in this sequential form. It actually works in a wholly merged form in which it only needs to store one section for each of the operands p and q and two consecutive sections for the result r.Algorithm 3:Computing regularized Boolean operations on the EVM.
Input:The nD-OPPsp and q expressed in the nD-EVM.The number n of dimensions and regularized Boolean operation op.Output:The output nD-OPP r, such that r =p op*q, codified as an nD-EVM.ProcedureBooleanOperation(EVM p, EVM q, BooleanOperator op, int n)EVM sP, sQ// Current sections of p and q respectively.EVM hvl// I/O couplet.boolean fromP, fromQ// flags for the source of the couplet hvl.CoordType coord// the common coordinate of couplets.EVM r, sRprev, sRcurr// nD-OPP r and two of its sections.if(n = 1)then// Base casereturnBooleanOperation1D(p, q, op)elsen = n-1sP = InitEVM( )sQ = InitEVM( )sRcurr = InitEVM( )NextObject(p, q, coord, fromP, fromQ)while(Not(EndEVM(p)) and Not(EndEVM(q)))if(fromP = true)thenhvl = ReadHvl(p)sP = GetSection(sP, hvl)end-of-ifif(fromQ = true)thenhvl = ReadHvl(q)sQ = GetSection(sQ, hvl)end-of-ifsRprev = sRcurrsRcurr = BooleanOperation(sP,sQ,op,n)// Recursive callhvl = GetHvl(sRprev, sRcurr)SetCoord(hvl, coord)PutHvl(hvl, r)NextObject(p, q, coord, fromP, fromQ)end-of-whilewhile(Not(EndEVM(p)))hvl = ReadHvl(p)PutBool(hvl, r, op)end-of-whilewhile(Not(EndEVM(q)))hvl = ReadHvl(q)PutBool(hvl, r, op)end-of-whilereturnrend-of-ifend-of-procedureThe following are some functions present in Algorithm3 but not defined previously.(i)
FunctionBooleanOperation1D performs 1D Boolean operations between p and q that are two 1D-OPPs.(ii)
ProcedureNextObject considers both input objects p and q and returns the common coord value of the next hvl to process, using function GetCoord. It also returns two flags, fromP and fromQ, which signal from which of the operands (both inclusive) is the next hvl to come.(iii)
The main loop of procedureBooleanOperation gets couplets from p and/or q, using function GetSection. These sections are recursively processed to compute, according to Corollary 3.24, the corresponding section of r, sRcurr. Since two consecutive sections, sRprev and sRcurr, are kept, then the projection of the resulting hvl, is obtained by means of function GetHvl, and then, it is correctly positioned by procedure SetCoord.When the end of one of the polytopesp or q is reached then the main iteration finishes, and the remaining couplets of the other polytope are either appended or not to the resulting polytope depending on the Boolean operation considered. Procedure PutBool performs this appending process.


### 3.5. Hypervoxelizations tonD-EVM Conversion

First, consider the following.Corollary 3.26 (see [10, 11]).
Letp and q be two disjoint  or quasi disjoint nD-OPPs having EVMn (p) and EVMn (q) as their respective Extreme Vertices Models, then EVMn(p∪q)=EVMn(p)⊗EVMn(q).As previously commented in the introduction of this paper, a hypervoxelization is a set of quasi-disjoint black and white hypervoxels each one being a convex orthogonal polytope. Since the set of black hypervoxels represents annD-OPP p we have [10](3.16)p=⋃λBlackHypervoxelλ.
For each black hypervoxel it should be possible to generate a list of its 2n vertices. Because all of these 2n vertices are Extreme Vertices, and by considering Corollary 3.26, all we have to do is [10](3.17)EVMn(p)=EVMn(⋃λBlackHypervoxelλ)=⊗λEVMn(BlackHypervoxelλ).
This provides a straight and simple method for converting a hypervoxelization to the nD-EVM.


## 3.1. The n-Dimensional Orthogonal Pseudo-Polytopes (nD-OPPs)

Definition 3.1 (see [13]).
ASingular n-dimensional hyper-box in ℝn is given by the continuous function
(3.1)In:[0,1]n→[0,1]n,x~In(x)=x.
A general singular k-dimensional hyper-box in the closed set A⊂ℝn is the continuous function
(3.2)c:[0,1]k→A.Definition 3.2 (see [13]).
For alli,1≤i≤n,the two singular(n-1)D hyper-boxes I(i,0)n and I(i,1)n are defined as follows. If x∈[0,1]n-1, then I(i,0)n(x)=(x1,…,xi-1,0,xi,…,xn-1) and I(i,1)n(x)=(x1,…,xi-1,1,xi,…,xn-1).Definition 3.3 (see [13]).
Theorientationof an (n-1)D cell c∘I(i,α)n is given by(-1)α+i. It is said cell c∘I(i,α)n is oriented when it is expressed by the scalar-function product (-1)i+α·c∘I(i,α)n.Definition 3.4 (see [13]).
A formal linear combination of general singularkD hyper-boxes,1 ≤k≤n, for a closed setAis called ak-chain.Definition 3.5 (see [13]).
Theboundary of an n-chain∑cj, where each cj is a general singular nD hyper-box, is given by
(3.3)∂(∑cj)=∑∂(cj)=∑(∑i=1n(∑α=0,1(-1)i+α·cj∘I(i,α)n)).Definition 3.6.
A collectionc1, c2, …, ck,1 ≤k≤ 2n, of general singular nD hyper-boxes is acombination ofnD hyper-boxesif and only if
(3.4)[⋂α=1kcα([0,1]n)=(0,…,0︸n)]∧[(∀i,j,i≠j,1≤i,j≤k)(ci([0,1]n)≠cj([0,1]n))].In the above definition the first part of the conjunction establishes that the intersection between all thenD general singular hyper-boxes is the origin, while the second part establishes that there are not overlapping nD hyper-boxes.Definition 3.7.
Ann-dimensional orthogonal pseudo-polytopep, or just an nD-OPPp, is an n-chain composed by nD hyper-boxes arranged in such way that by selecting a vertex, in any of these hyper-boxes, it describes a combination of nD hyper-boxes (Definition 3.6) composed up to 2n hyper-boxes.


## 3.2.nD-EVM’s Fundamentals

Definition 3.8.
Letcbe a combination of hyper-boxes in the n-Dimensional space. An Odd Adjacency Edgeofc, or just anOdd Edge, is an edge with an odd number of incident hyper-boxes of c.Conversely, if an edge has an even number of incident hyper-boxes of c, it is called Even Adjacency Edge, or just Even Edge.Definition 3.9.
Abrinkorextended edge is the maximal uninterrupted segment, built out of a sequence of collinear and contiguous odd edges of an nD-OPP.From the above definition, every even edge of annD-OPP does not belong to brinks. On the other hand, every brink consists of m odd edges,m≥ 1, and contains m+ 1 vertices. Two of these vertices are at either extreme of the brink and the remaining m-1 are interior vertices.Definition 3.10.
The ending vertices of all the brinks inp will be called Extreme Vertices of an nD-OPP p.  EV(p)will denote to the set of Extreme Vertices of p.Property 3.11.
Any extreme vertex of an n D-OPP, n≥ 1, when is locally described by a set of surrounding n D hyper-boxes, has exactly n incident linearly independent odd edges.Figure2 shows an example of a 3D-OPP p. Vertices v1 and v2 are nonextreme vertices because, in the case of v1, it has six incident odd edges, while vertex v2 has four incident coplanar odd edges (see Property 3.11). In the figure can be also appreciated that exactly three linearly independent odd edges are incident to the remaining vertices, actually, the Extreme Vertices of p.Figure 2
Example of a 3D-OPP and its set of Extreme Vertices (Continuous lines indicate odd edges, dotted lines indicate even edges, black points correspond to extreme vertices, and white points correspond to non extreme vertices).The brinks in annD-OPP p can be classified according to the main axis to which they are parallel. Since the extreme vertices mark the end of brinks in the n orthogonal directions, is that any of the n possible sets of brinks parallel to Xi-axis, 1 ≤i≤n, produce to the same set EV(p). See in Figure 3(a) the brinks parallel to X2-axis for the 3D-OPP originally presented in Figure 2.Illustrating some EVM concepts over a 3D-OPP (See text for details).
(a)(b)(c)(d)(e)(f)Definition 3.12.
Letp be an nD-OPP. A kD extended hypervolume of p, 1 <k<n, denoted by ϕ(p), is the maximal set of kD cells of p that lies in a kD space, such that a kD cell e0 belongs to a kD extended hypervolume if and only if e0 belongs to an (n-1)D cell present in ∂(p) (see Definition 3.5), that is,
(3.5)(e0∈ϕ(p))⇔(∃c,cbelongsto∂(p))(e0([0,1]k)⊆c([0,1]n-1)).Definition 3.13.
Letp be an nD-OPP. The Extreme Vertices Model of p, denoted by EVMn(p), is defined as the model as only stores to all the extreme vertices of p.Let Q be a finite set of points inℝ3. In [10] was defined the ABC-sorted set of Q as the set resulting from sorting Q according to coordinate A, then to coordinate B, and then to coordinate C. For instance, a set Q can be ABC-sorted in six different ways. Now, let p be a 3D-OPP. According to [10] the Extreme Vertices Model of p, EVM3(p), denotes the ABC sorted set of the extreme vertices of p. Then EVM3(p) = EV(p) except by the fact that coordinates of points in EV(p) are not necessarily sorted. In general, it is always assumed that coordinates of extreme vertices in the Extreme Vertices Model of an nD-OPP p, EVMn(p), have a fixed coordinates ordering. Moreover, when an operation requires manipulating two EVMs, it is assumed that both sets have the same coordinates ordering.Definition 3.14.
TheProjection Operator for (n-1)D cells, points, and set of points is, respectively, defined as follows.(i)
Letc(I(i,α)n(x))=(x1,…,xn) be an (n-1)D cell embedded in the nD space. Let πj(c(I(i,α)n(x))) denote the projection of the cell c(I(i,α)n(x)) onto an (n-1)D space embedded in nD space whose supporting hyperplane is perpendicular to Xj-axis
(3.6)πj(c(I(i,α)n(x)))=(x1,…,x̂j,…,xn).(ii)
Letv=(x1,…,xn) a point in ℝn. The projection of that point in the (n-1)D space, denoted by πj(v), is given by:
(3.7)πj(v)=(x1,…,x̂j,…,xn).(iii)
Let Q be a set of points inℝn. The projection of the points in Q, denoted by πj(Q), is defined as the set of points in ℝn-1 such that(3.8)πj(Q)={p∈ℝn-1:p=πj(x),x∈Q⊂ℝn},
In all the cases x̂j is the coordinate corresponding to Xj-axis to be suppressed.Definition 3.15.
Consider annD-OPP p as follows.(i)
Letnpi be the number of distinct coordinates present in the vertices of p along Xi-axis, 1 ≤i≤n.(ii)
LetΦki(p) be the kth (n-1)D extended hypervolume, or just a (n-1)D couplet, of p which is perpendicular to Xi-axis, 1 ≤k≤npi.See in Figure3(b) the set of 2D-couplets perpendicular to X2-axis for the 3D-OPP presented in Figure 2.Definition 3.16.
A slice is the region contained in annD-OPP p between two consecutive couplets of p. Sliceki(p) will denote to the kth slice of p which is bounded by Φki(p)andΦk+1i(p), 1 ≤k<npi.Definition 3.17.
Asection is the (n-1)D-OPP, n> 1, resulting from the intersection between an nD-OPP p and an (n-1)D hyperplane perpendicular to the coordinate axis Xi,n≥i≥ 1, which does not coincide with any (n-1)D-couplet of p. A section will be calledexternalorinternal section of p if it is empty or not, respectively.  Ski(p) will refer to the kth section of p between Φki(p) and Φk+1i(p), 1 ≤k<npi. Moreover, S0i(p) andSnpii(p)  will refer to the empty sections of p before  Φ1i(p)  and after ofΦnpii(p), respectively.Property 3.18.
Letp be an n D-OPP. All the (n -1)D hyperplanes perpendicular to Xi -axis, 1 ≤i ≤n, which intersect to Sliceki(p) give the same section Ski(p).The Figures3(c), 3(d), and 3(e) show the slices for a 3D-OPP (originally presented in Figure 2) according to the supporting planes of its 2D-couplets perpendicular to X2-axis. Figure 3(f) presents its corresponding set of internal sections perpendicular to X2-axis.


### 3.2.1. A Note about Regularized Boolean Operations

Independently of the scheme we consider for the representation ofnD polytopes, it should be feasible to combine them in order to compose new objects [14]. One of the most common methods to combine polytopes is the set theoretical Boolean operations, as the Union, Difference, Intersection, and Exclusive OR. However, the application of an ordinary set theoretical Boolean operation on two polytopes does not necessarily produce a polytope. For example, the ordinary intersection between two cubes with only a common vertex is a point. Instead of using ordinary set theoretical Boolean operators, the Regularized Boolean Operators [15, 16] will be used. The practical purpose of regularization of polytope models is to make them dimensionally homogeneous [17]. The regularization operation can be defined as Regularized(S) = Closure(Interior(S)) which results in a closed regular set. Each regularized Boolean operator is defined in function of an ordinary operator in the following way:(3.9)Aop*B=Closure(Interior(AopB)).
These operators are defined as the closure of the interior of the corresponding set theoretical Boolean operation [16, 18]. In this way, the regularized operations between polytopes always will generate polytopes or a null object (the empty set) [17].


### 3.2.2. Computing Couplets from Sections

Theorem 3.19.
The projection of the set of (n -1)D couplets,πi(Φki(p)),  1 ≤i  ≤n, of an nD-OPP p, can be obtained by computing the regularized XOR (⊗*) between the projections of its previous πi(Sk-1i(p)) and next πi(Ski(p)) sections, that is, πi(Φki(p))=πi(Sk-1i(p))⊗*πi(Ski(p)), for all k∈[1,npi].


### 3.2.3. Computing Sections from Couplets

Theorem 3.20.
The projection of any section,πi(Ski(p)), of an nD-OPPp, can be obtained by computing the regularized XOR between the projection of its previous section, πi(Sk-1i(p)), and the projection of its previous couplet πi(Φki(p)):
(3.10)S0i(p)=∅,πi(Ski(p))=πi(Sk-1i(p))⊗*πi(Φki(p)),∀k∈[1,npi].


### 3.2.4. The Regularized XOR Operation on thenD-EVM

Theorem 3.21.
Letp and q be two nD-OPPs having EVMn(p) and EVMn(q) as their respective Extreme Vertices Models in nD space, then EVMn(p⊗*q)=EVMn(p)⊗EVMn(q).This result allows expressing formulae for computingnD-OPPs sections from couplets and viceversa by means of their corresponding Extreme Vertices Models. They are obtained by combining Theorem 3.21 with Theorem 3.19 and Theorem 3.21 with Theorem 3.20, respectively.Corollary 3.22.
One has thatEVMn-1(πi(Φki(p)))=EVMn-1(πi(Sk-1i(p)))⊗EVMn-1(πi(Ski(p))).Corollary 3.23.
One has thatEVMn-1(πi(Ski(p)))=EVMn-1(πi(Sk-1i(p)))⊗EVMn-1(πi(Φki(p))).


### 3.2.5. The Regularized Boolean Operations on thenD-EVM

Corollary 3.24.
Letp and q be two nD-OPPs and r = p op*q, where op* is in {∪*,∩*,-*,⊗*}. Then πi(Ski(r))=πi(Ski(p))op*πi(Ski(q)). Moreover, if all these sections lie in the same (n -1)D hyperplane then Ski(r)=Ski(p)op*Ski(q).Now we present the following.Theorem 3.25.
A regularized Boolean operation, op*, where op*∈{∪*,∩*,-*,⊗*}, over two nD-OPPs p and q, both expressed in the nD-EVM, can be carried out by means of the same op* applied over their own sections, expressed through their Extreme Vertices Models, which are (n-1)D-OPPs.This result leads into a recursive process for computing the Regularized Boolean operations using thenD-EVM, which descends on the number of dimensions [10]. The base or trivial case of the recursion corresponds to the 1D-Boolean operations which can be performed using direct methods. In Section 3.4.2 will be described an algorithm for performing Regularized Boolean operations under the nD-EVM which implements the above results.


## 3.2.1. A Note about Regularized Boolean Operations

Independently of the scheme we consider for the representation ofnD polytopes, it should be feasible to combine them in order to compose new objects [14]. One of the most common methods to combine polytopes is the set theoretical Boolean operations, as the Union, Difference, Intersection, and Exclusive OR. However, the application of an ordinary set theoretical Boolean operation on two polytopes does not necessarily produce a polytope. For example, the ordinary intersection between two cubes with only a common vertex is a point. Instead of using ordinary set theoretical Boolean operators, the Regularized Boolean Operators [15, 16] will be used. The practical purpose of regularization of polytope models is to make them dimensionally homogeneous [17]. The regularization operation can be defined as Regularized(S) = Closure(Interior(S)) which results in a closed regular set. Each regularized Boolean operator is defined in function of an ordinary operator in the following way:(3.9)Aop*B=Closure(Interior(AopB)).
These operators are defined as the closure of the interior of the corresponding set theoretical Boolean operation [16, 18]. In this way, the regularized operations between polytopes always will generate polytopes or a null object (the empty set) [17].


## 3.2.2. Computing Couplets from Sections

Theorem 3.19.
The projection of the set of (n -1)D couplets,πi(Φki(p)),  1 ≤i  ≤n, of an nD-OPP p, can be obtained by computing the regularized XOR (⊗*) between the projections of its previous πi(Sk-1i(p)) and next πi(Ski(p)) sections, that is, πi(Φki(p))=πi(Sk-1i(p))⊗*πi(Ski(p)), for all k∈[1,npi].


## 3.2.3. Computing Sections from Couplets

Theorem 3.20.
The projection of any section,πi(Ski(p)), of an nD-OPPp, can be obtained by computing the regularized XOR between the projection of its previous section, πi(Sk-1i(p)), and the projection of its previous couplet πi(Φki(p)):
(3.10)S0i(p)=∅,πi(Ski(p))=πi(Sk-1i(p))⊗*πi(Φki(p)),∀k∈[1,npi].


## 3.2.4. The Regularized XOR Operation on thenD-EVM

Theorem 3.21.
Letp and q be two nD-OPPs having EVMn(p) and EVMn(q) as their respective Extreme Vertices Models in nD space, then EVMn(p⊗*q)=EVMn(p)⊗EVMn(q).This result allows expressing formulae for computingnD-OPPs sections from couplets and viceversa by means of their corresponding Extreme Vertices Models. They are obtained by combining Theorem 3.21 with Theorem 3.19 and Theorem 3.21 with Theorem 3.20, respectively.Corollary 3.22.
One has thatEVMn-1(πi(Φki(p)))=EVMn-1(πi(Sk-1i(p)))⊗EVMn-1(πi(Ski(p))).Corollary 3.23.
One has thatEVMn-1(πi(Ski(p)))=EVMn-1(πi(Sk-1i(p)))⊗EVMn-1(πi(Φki(p))).


## 3.2.5. The Regularized Boolean Operations on thenD-EVM

Corollary 3.24.
Letp and q be two nD-OPPs and r = p op*q, where op* is in {∪*,∩*,-*,⊗*}. Then πi(Ski(r))=πi(Ski(p))op*πi(Ski(q)). Moreover, if all these sections lie in the same (n -1)D hyperplane then Ski(r)=Ski(p)op*Ski(q).Now we present the following.Theorem 3.25.
A regularized Boolean operation, op*, where op*∈{∪*,∩*,-*,⊗*}, over two nD-OPPs p and q, both expressed in the nD-EVM, can be carried out by means of the same op* applied over their own sections, expressed through their Extreme Vertices Models, which are (n-1)D-OPPs.This result leads into a recursive process for computing the Regularized Boolean operations using thenD-EVM, which descends on the number of dimensions [10]. The base or trivial case of the recursion corresponds to the 1D-Boolean operations which can be performed using direct methods. In Section 3.4.2 will be described an algorithm for performing Regularized Boolean operations under the nD-EVM which implements the above results.


## 3.3. Basic Algorithms for thenD-EVM

Now, we introduce some primitive operations which are in fact based on those originally presented in [10]. When an operation requires manipulating two EVMs, it is assumed that both sets have the same coordinates ordering. In the following, XA-axis refers to the nD space’s coordinate axis associated to the first coordinate present in the vertices of EVMn(p). For example, given coordinates ordering X1X2X3, for a 3D-OPP, then XA=X1. (i)
InitEVM( ): returns the empty set.(ii)
PutHvl(EVM hvl, EVM p): appends and (n-1)D couplet hvl, embedded in nD space and perpendicular to XA-axis, to the nD-EVM p.(iii)
ReadHvl(EVM p): extracts and returns the next (n-1)D couplet perpendicular to XA-axis from p.(iv)
EndEVM(EVM p): returns true if the end of p along XA-axis has been reached, otherwise, returns false.(v)
SetCoord(EVM hvl, CoordType coord): sets the XA-coordinate to coord on every vertex of the (n-1)D couplet hvl. For coord = 0, it performs the projection πA(p).CoordType is the chosen type for the vertex coordinates.(vi)
GetCoord(EVM hvl): returns the common XA-coordinate of the (n-1)D couplet hvl.(vii)
GetCoordNextHvl(EVM p): returns the common XA-coordinate of the next available (n-1)D couplet, perpendicular to XA-axis, from p.(viii)
MergeXor(EVM p, EVM q): applies the Exclusive OR operation to the vertices of p and q and returns the resulting EVM.Since the EVM is a sorted model, MergeXor function consists in a simple merging-like algorithm, and therefore, it runs on linear time [10]. Its complexity is given by O(Card(EVMn(p)) + Card(EVMn(q))) because each vertex from EVMn(p) and EVMn(q) needs to be processed just once. Moreover, according to Theorem 3.21, the resulting set corresponds to the regularized XOR operation between p and q.From the above primitive operations, and specifically MergeXor, the following pair of algorithms can be easily derived ([10, 11]).(i)
GetHvl(EVM Si, EVM Sj): implements Corollary 3.22, and returns the projection of the couplet between consecutive sections Si and Sj.(ii)
GetSection(EVM S, EVM hvl): implements Corollary 3.23, and returns the projection of the next section of an nD-OPP whose previous section is S.the Algorithm1 computes the sequence of sections of an nD-OPP p from its nD-EVM using the previous functions [10, 11]. It sequentially reads the projections of the (n-1)D couplets hvl of the polytope p. Then it computes the sequence of sections using function GetSection. Each pair of sections Si and Sj (the previous and next sections about the current hvl) is processed by a generic processing procedure (called Process), which performs the desired actions upon Si and Sj (note that some processes may only need one of such sections).Algorithm 1:Computing the sequence of sections from an nD-OPP p.
Input:AnnD-EVM p.ProcedureEVM_to_SectionSequence(EVM p)EVM hvl// Current couplet.EVM Si, Sj// Previous and next sections about hvl.hvl = InitEVM( )Si = InitEVM( )Sj = InitEVM( )hvl = ReadHvl(p)while(Not(EndEVM(p)))Sj = GetSection(Si, hvl)Process(Si, Sj)Si = Sjhvl = ReadHvl(p)// Read next couplet.end-of-whileend-of-procedure


## 3.4. Interrogating and ManipulatingnD-OPPs Represented via the nD-EVM

### 3.4.1. Computing the Content of annD-OPP

AnnD hyperprism can be generated by the parallel motion of an (n-1)D polytope; it is bounded by the (n-1)D polytope in its initial and final positions and by several (n-1)D hyperprisms [19]. Consider an nD hyperprism Pn whose base is an (n-1)D polytope Pn-1 of content Cn-1. If hn is the distance between its bases, that is, the height of the hyperprism, then its content is given by [19](3.11)Content(Pn)=Content(Pn-1)·hn=Cn-1·hn.If it is the case where Pn-1 is an (n-1)D hyperprism with height hn-1 generated by the parallel motion of an (n-2)D polytope Pn-2, then Cn-1 is given by the expression Cn-1 = Cn-2·hn-1, where Cn-2 is the content of Pn-2. This last expression yields to rewrite the above equation as(3.12)Content(Pn)=(Content(Pn-2)·hn-1)·hn=(Cn-2·hn-1)·hn.By considering that each (n-k)D hyperprism Pn-k is generated by the parallel motion of an (n-k-1)D hyperprism Pn-k-1, where k = 0, 1, 2, …, n-1, then we have that the content of Pn can be computed according to the formula(3.13)Content(Pn)={h1,n=1,Content(Pn-1)·hn,n>1,
where hn is the height of hyperprism Pn. In the base case, where n = 1, the content of a segment is given directly by its “height”, that is, the distance between its two boundary points.The previous idea is extended in order to compute the content ofnD space enclosed by an nD-OPP. In this case we will consider the partition induced by its slices (Definition 3.16). A slice can be seen as a set of one or more disjoint nD hyperprisms whose (n-1)D base is the slice’s section. As pointed out in [10] the volume of a 3D-OPP p can be computed as the sum of the volumes of its 3D slices, where the volume of a Sliceki(p), is given by the product between the area of its respective section Ski(p) (the 2D base of Sliceki(p)) and the distance between Φki(p) and Φk+1i(p) (the height of the 3D prism Sliceki(p)). Now let q = Ski(p). The area of the 2D-OPP q (see Figure 4 for an example) can be computed as the sum of the areas of its 2D slices, where the area of a Sliceki(q), is given by the product between the length of its respective section Ski(q) (the 1D base of Sliceki(q)) and the distance between Φki(q) and Φk+1i(q) (the height of the “2D prism” Sliceki(p)). Finally let r = Ski(q). In the basic case the length of the 1D-OPP r is computed as the sum of the lengths of its brinks.Figure 4
A 2D-OPPq whose area is being computed (see text for details).Letp be an nD-OPP. The nD space enclosed by p, denoted by Content(n)(p), can be computed as the sum of the contents of its nD slices [11](3.14)Content(n)(p)={Length(p)n=1,∑k=1npi-1Content(n-1)(Ski(p))·dist(Φki(p),Φk+1i(p))n>1.
Algorithm 2 implements the above equation in order to compute the content of nD space enclosed by an nD-OPP p expressed through the nD-EVM [10, 11].Algorithm 2:Computing the content of nD space enclosed by an OPP.
Input:AnnD-EVM p.The number n of dimensions.Output:The content of nD space enclosed by p.ProcedureContent(EVM p, int n)real cont = 0.0// The content of nD space enclosed by p.EVM hvl1, hvl2// Consecutive couplets perpendicular to XA-axis.EVM s// Current section of p.if(n = 1)then returnLength(p)// Base case: p is a 1D-OPP.elses = InitEVM( )hvl1 = ReadHvl(p)while(Not(EndEVM(p)))hvl2 = ReadHvl(p)s = GetSection(s, hvl1)cont = cont + Content(s, n-1) * dist(hvl1, hvl2)hvl1 = hvl2end-of-whilereturncontend-of-elseend-of-procedure


### 3.4.2. The Boolean Operations Algorithm for thenD-EVM

Letp and q be two nD-OPPs represented through the nD-EVM, and let op* be a regularized Boolean operator in {∪*,∩*,-*,⨂*}. The algorithm, originally presented in [10] and based on Theorem 3.25, computes the resulting nD-OPP r = p op* q. Note that r = p ⊗*q can also be trivially performed using Theorem 3.21 [10]. The idea behind the algorithm is the following.(i)
The sequence of sections fromp and q, perpendicular to XA-axis, is obtained first, based on Theorem 3.20.(ii)
Then, according to Corollary3.24, every section of r can recursively be computed as
(3.15)SkA(r)=SkA(p)op*SkA(q).(iii)
Finally,r can be obtained from its sequence of sections, perpendicular to XA-axis, according to Theorem 3.19.Nevertheless, Algorithm3 does not work in this sequential form. It actually works in a wholly merged form in which it only needs to store one section for each of the operands p and q and two consecutive sections for the result r.Algorithm 3:Computing regularized Boolean operations on the EVM.
Input:The nD-OPPsp and q expressed in the nD-EVM.The number n of dimensions and regularized Boolean operation op.Output:The output nD-OPP r, such that r =p op*q, codified as an nD-EVM.ProcedureBooleanOperation(EVM p, EVM q, BooleanOperator op, int n)EVM sP, sQ// Current sections of p and q respectively.EVM hvl// I/O couplet.boolean fromP, fromQ// flags for the source of the couplet hvl.CoordType coord// the common coordinate of couplets.EVM r, sRprev, sRcurr// nD-OPP r and two of its sections.if(n = 1)then// Base casereturnBooleanOperation1D(p, q, op)elsen = n-1sP = InitEVM( )sQ = InitEVM( )sRcurr = InitEVM( )NextObject(p, q, coord, fromP, fromQ)while(Not(EndEVM(p)) and Not(EndEVM(q)))if(fromP = true)thenhvl = ReadHvl(p)sP = GetSection(sP, hvl)end-of-ifif(fromQ = true)thenhvl = ReadHvl(q)sQ = GetSection(sQ, hvl)end-of-ifsRprev = sRcurrsRcurr = BooleanOperation(sP,sQ,op,n)// Recursive callhvl = GetHvl(sRprev, sRcurr)SetCoord(hvl, coord)PutHvl(hvl, r)NextObject(p, q, coord, fromP, fromQ)end-of-whilewhile(Not(EndEVM(p)))hvl = ReadHvl(p)PutBool(hvl, r, op)end-of-whilewhile(Not(EndEVM(q)))hvl = ReadHvl(q)PutBool(hvl, r, op)end-of-whilereturnrend-of-ifend-of-procedureThe following are some functions present in Algorithm3 but not defined previously.(i)
FunctionBooleanOperation1D performs 1D Boolean operations between p and q that are two 1D-OPPs.(ii)
ProcedureNextObject considers both input objects p and q and returns the common coord value of the next hvl to process, using function GetCoord. It also returns two flags, fromP and fromQ, which signal from which of the operands (both inclusive) is the next hvl to come.(iii)
The main loop of procedureBooleanOperation gets couplets from p and/or q, using function GetSection. These sections are recursively processed to compute, according to Corollary 3.24, the corresponding section of r, sRcurr. Since two consecutive sections, sRprev and sRcurr, are kept, then the projection of the resulting hvl, is obtained by means of function GetHvl, and then, it is correctly positioned by procedure SetCoord.When the end of one of the polytopesp or q is reached then the main iteration finishes, and the remaining couplets of the other polytope are either appended or not to the resulting polytope depending on the Boolean operation considered. Procedure PutBool performs this appending process.


## 3.4.1. Computing the Content of annD-OPP

AnnD hyperprism can be generated by the parallel motion of an (n-1)D polytope; it is bounded by the (n-1)D polytope in its initial and final positions and by several (n-1)D hyperprisms [19]. Consider an nD hyperprism Pn whose base is an (n-1)D polytope Pn-1 of content Cn-1. If hn is the distance between its bases, that is, the height of the hyperprism, then its content is given by [19](3.11)Content(Pn)=Content(Pn-1)·hn=Cn-1·hn.If it is the case where Pn-1 is an (n-1)D hyperprism with height hn-1 generated by the parallel motion of an (n-2)D polytope Pn-2, then Cn-1 is given by the expression Cn-1 = Cn-2·hn-1, where Cn-2 is the content of Pn-2. This last expression yields to rewrite the above equation as(3.12)Content(Pn)=(Content(Pn-2)·hn-1)·hn=(Cn-2·hn-1)·hn.By considering that each (n-k)D hyperprism Pn-k is generated by the parallel motion of an (n-k-1)D hyperprism Pn-k-1, where k = 0, 1, 2, …, n-1, then we have that the content of Pn can be computed according to the formula(3.13)Content(Pn)={h1,n=1,Content(Pn-1)·hn,n>1,
where hn is the height of hyperprism Pn. In the base case, where n = 1, the content of a segment is given directly by its “height”, that is, the distance between its two boundary points.The previous idea is extended in order to compute the content ofnD space enclosed by an nD-OPP. In this case we will consider the partition induced by its slices (Definition 3.16). A slice can be seen as a set of one or more disjoint nD hyperprisms whose (n-1)D base is the slice’s section. As pointed out in [10] the volume of a 3D-OPP p can be computed as the sum of the volumes of its 3D slices, where the volume of a Sliceki(p), is given by the product between the area of its respective section Ski(p) (the 2D base of Sliceki(p)) and the distance between Φki(p) and Φk+1i(p) (the height of the 3D prism Sliceki(p)). Now let q = Ski(p). The area of the 2D-OPP q (see Figure 4 for an example) can be computed as the sum of the areas of its 2D slices, where the area of a Sliceki(q), is given by the product between the length of its respective section Ski(q) (the 1D base of Sliceki(q)) and the distance between Φki(q) and Φk+1i(q) (the height of the “2D prism” Sliceki(p)). Finally let r = Ski(q). In the basic case the length of the 1D-OPP r is computed as the sum of the lengths of its brinks.Figure 4
A 2D-OPPq whose area is being computed (see text for details).Letp be an nD-OPP. The nD space enclosed by p, denoted by Content(n)(p), can be computed as the sum of the contents of its nD slices [11](3.14)Content(n)(p)={Length(p)n=1,∑k=1npi-1Content(n-1)(Ski(p))·dist(Φki(p),Φk+1i(p))n>1.
Algorithm 2 implements the above equation in order to compute the content of nD space enclosed by an nD-OPP p expressed through the nD-EVM [10, 11].Algorithm 2:Computing the content of nD space enclosed by an OPP.
Input:AnnD-EVM p.The number n of dimensions.Output:The content of nD space enclosed by p.ProcedureContent(EVM p, int n)real cont = 0.0// The content of nD space enclosed by p.EVM hvl1, hvl2// Consecutive couplets perpendicular to XA-axis.EVM s// Current section of p.if(n = 1)then returnLength(p)// Base case: p is a 1D-OPP.elses = InitEVM( )hvl1 = ReadHvl(p)while(Not(EndEVM(p)))hvl2 = ReadHvl(p)s = GetSection(s, hvl1)cont = cont + Content(s, n-1) * dist(hvl1, hvl2)hvl1 = hvl2end-of-whilereturncontend-of-elseend-of-procedure


## 3.4.2. The Boolean Operations Algorithm for thenD-EVM

Letp and q be two nD-OPPs represented through the nD-EVM, and let op* be a regularized Boolean operator in {∪*,∩*,-*,⨂*}. The algorithm, originally presented in [10] and based on Theorem 3.25, computes the resulting nD-OPP r = p op* q. Note that r = p ⊗*q can also be trivially performed using Theorem 3.21 [10]. The idea behind the algorithm is the following.(i)
The sequence of sections fromp and q, perpendicular to XA-axis, is obtained first, based on Theorem 3.20.(ii)
Then, according to Corollary3.24, every section of r can recursively be computed as
(3.15)SkA(r)=SkA(p)op*SkA(q).(iii)
Finally,r can be obtained from its sequence of sections, perpendicular to XA-axis, according to Theorem 3.19.Nevertheless, Algorithm3 does not work in this sequential form. It actually works in a wholly merged form in which it only needs to store one section for each of the operands p and q and two consecutive sections for the result r.Algorithm 3:Computing regularized Boolean operations on the EVM.
Input:The nD-OPPsp and q expressed in the nD-EVM.The number n of dimensions and regularized Boolean operation op.Output:The output nD-OPP r, such that r =p op*q, codified as an nD-EVM.ProcedureBooleanOperation(EVM p, EVM q, BooleanOperator op, int n)EVM sP, sQ// Current sections of p and q respectively.EVM hvl// I/O couplet.boolean fromP, fromQ// flags for the source of the couplet hvl.CoordType coord// the common coordinate of couplets.EVM r, sRprev, sRcurr// nD-OPP r and two of its sections.if(n = 1)then// Base casereturnBooleanOperation1D(p, q, op)elsen = n-1sP = InitEVM( )sQ = InitEVM( )sRcurr = InitEVM( )NextObject(p, q, coord, fromP, fromQ)while(Not(EndEVM(p)) and Not(EndEVM(q)))if(fromP = true)thenhvl = ReadHvl(p)sP = GetSection(sP, hvl)end-of-ifif(fromQ = true)thenhvl = ReadHvl(q)sQ = GetSection(sQ, hvl)end-of-ifsRprev = sRcurrsRcurr = BooleanOperation(sP,sQ,op,n)// Recursive callhvl = GetHvl(sRprev, sRcurr)SetCoord(hvl, coord)PutHvl(hvl, r)NextObject(p, q, coord, fromP, fromQ)end-of-whilewhile(Not(EndEVM(p)))hvl = ReadHvl(p)PutBool(hvl, r, op)end-of-whilewhile(Not(EndEVM(q)))hvl = ReadHvl(q)PutBool(hvl, r, op)end-of-whilereturnrend-of-ifend-of-procedureThe following are some functions present in Algorithm3 but not defined previously.(i)
FunctionBooleanOperation1D performs 1D Boolean operations between p and q that are two 1D-OPPs.(ii)
ProcedureNextObject considers both input objects p and q and returns the common coord value of the next hvl to process, using function GetCoord. It also returns two flags, fromP and fromQ, which signal from which of the operands (both inclusive) is the next hvl to come.(iii)
The main loop of procedureBooleanOperation gets couplets from p and/or q, using function GetSection. These sections are recursively processed to compute, according to Corollary 3.24, the corresponding section of r, sRcurr. Since two consecutive sections, sRprev and sRcurr, are kept, then the projection of the resulting hvl, is obtained by means of function GetHvl, and then, it is correctly positioned by procedure SetCoord.When the end of one of the polytopesp or q is reached then the main iteration finishes, and the remaining couplets of the other polytope are either appended or not to the resulting polytope depending on the Boolean operation considered. Procedure PutBool performs this appending process.


## 3.5. Hypervoxelizations tonD-EVM Conversion

First, consider the following.Corollary 3.26 (see [10, 11]).
Letp and q be two disjoint  or quasi disjoint nD-OPPs having EVMn (p) and EVMn (q) as their respective Extreme Vertices Models, then EVMn(p∪q)=EVMn(p)⊗EVMn(q).As previously commented in the introduction of this paper, a hypervoxelization is a set of quasi-disjoint black and white hypervoxels each one being a convex orthogonal polytope. Since the set of black hypervoxels represents annD-OPP p we have [10](3.16)p=⋃λBlackHypervoxelλ.
For each black hypervoxel it should be possible to generate a list of its 2n vertices. Because all of these 2n vertices are Extreme Vertices, and by considering Corollary 3.26, all we have to do is [10](3.17)EVMn(p)=EVMn(⋃λBlackHypervoxelλ)=⊗λEVMn(BlackHypervoxelλ).
This provides a straight and simple method for converting a hypervoxelization to the nD-EVM.


## 4. Computing Discrete Compactness for annD-OPP Expressed in the nD-EVM

In the following it is assumed annD-OPP fits exactly in a hypervoxelization, where hypervoxels are unit nD hypercubes whose vertices have integer coordinates. Given a polytope p expressed in the nD-EVM, and in order to compute LC(p), that is, the number of shared (n-1)D cells between the m hypervoxels that originally described p, we start by processing its (n-1)D sections perpendicular to XA-axis. By considering a section, it can be determined the number of hypervoxels that originally described its corresponding slice. Furthermore, it is possible to obtain information about internal contacts, perpendicular to XA-axis, between the hypervoxels that described such nD slice. Let Sj be the section associated to SlicejA(p). Then, the following steps are performed.(i)
Let c1 and c2 be the common XA coordinates of previous and next couplets, perpendicular to XA-axis, about section Sj. Let nCoords = c2 – c1 – 1 be the number of integer coordinates between c1 and c2. In fact, nCoords = Card({c1 + 1, c1 + 2, …, c2 – 1}).(ii)
Because ofp’s assumed original representation, it is clear by computing the nD content of SlicejA(p) that it is obtained the number of black nD hypervoxels that originally defined it. Now, let H be an (n-1)D hyperplane perpendicular to XA-axis such that it intersects SlicejA(p) and does not coincide with the supporting hyperplanes of the previous and next couplets about section Sj. Assuming the common XA-coordinate of the points in H is in {c1 + 1, c1 + 2, …, c2 – 1}, and by computing the (n-1)D content of the projection of section Sj, there is obtained the number of those hypervoxels which have an (n-1)D boundary cell embedded in hyperplane H.(iii)
Finally, the number of internal contacts, perpendicular toXA-axis, between the hypervoxels that originally defined SlicejA(p), is given by the product of nCoords (the number of integer coordinates between the previous and next couplets about Sj) and the (n-1)D content of Sj.The above procedure determines the number of internal contacts, perpendicular toXA-axis, between the hypervoxels that originally composed to SlicejA(p). Now, we must determine the number of internal contacts ((n-1)D adjacencies) between those hypervoxels that belong to SlicejA(p) with hypervoxels in the next slice, that is, Slicej+1A(p). Those shared cells are embedded in the supporting (n-1)D hyperplane of the couplet between sections Sj and Sj+1.  (i)
The projections of consecutive sectionsSj and Sj+1 are intersected in such way that it is obtained an (n-1)D-OPP Sint.(ii)
The number of those (n-1)D boundary cells, embedded in the supporting (n-1)D hyperplane of the couplet between Sj and Sj+1, is given by computing the (n-1)D content of Sint. If Sint is empty then it implies that (1) one of the sections, Sj or Sj+1, is empty or (2) projections of Sj and Sj+1 are disjoint or quasi-disjoint. In both cases no (n-1)D contact occurs between SlicejA(p) and Slicej+1A(p).Algorithm4 implements the above procedures.Algorithm 4:Computing the number of (n-1)D adjacencies between the hypervoxels that originally defined an nD-OPP p.
Input:AnnD-EVM p and the number n of dimensions.Output:The number of internal contacts, perpendicular to the XA-axis, betweenthe hypervoxels that originally composed p.ProcedureInternalContacts(EVM p, int n)EVM hvl// Current couplet of p.EVMSi,Sj// Previous and next sections about hvl.EVMSint// The result of intersecting the projections of Si and Sj.int c1// Common XA-coordinate of couplet hvl.int c2// Common XA-coordinate of couplet next to hvl.int nCoords// Number of integer coordinates  between c1 and c2.int L = 0// Number of internal contacts ((n-1)D adjacencies).Si = InitEVM( )c1 = GetCoordNextHvl(p)hvl = ReadHvl(p)while(Not(EndEVM(p)))Sj = GetSection(Si, hvl)c2 = GetCoordNextHvl(p)nCoords =c2-c1-1L = L + nCoords * Content(Sj, n-1)Sint = BooleanOperation(Si,Sj, Intersection, n-1)L = L + Content(Sint, n-1)Si = Sjc1 = c2hvl = ReadHvl(p)// Read next couplet.end-of-whilereturnLend-of-procedureWe will clarify the way Algorithm4 works with the following example. Consider the object defined by the 3D boxes presented in Figure 5(a). The 3D grid where the object is embedded has dimensions 8×8×8. The coordinates of all the boxes’ vertices are in the set {0,1,…,8}3. When the boxes are united, according to the procedure described in Section 3.5, it is obtained the 3D-OPP p shown, as a wireframe model, in Figure 5(b). Its 3D-EVM is composed by 14 extreme vertices. Figure 5(c) shows p’s three couplets perpendicular to X1-axis, while Figure 5(d) presents its pair of internal sections, S11(p) and S21(p), also perpendicular to X1-axis. 2D section S11(p) is associated to Slice11(p) (see Figure 5(e)), while S21(p) is associated to Slice21(p) (Figure 5(f)). Suppose that 2D couplets Φ11(p),  Φ21(p), and Φ31(p) have common X1 coordinates given by 0, 4, and 8, respectively. Hence, the number of integer coordinates, along X1-axis, between couplets Φ11(p) and Φ21(p) is 3. Such coordinates are 1, 2, and 3. Now, consider the projection of section S11(p) (Figure 5(g)). Because the boxes in the original voxelization were unitary, then the area of S11(p), 64 u2, corresponds to the number of faces embedded in a plane intersecting Slice11(p) which does not coincide with Φ11(p) nor Φ21(p), and whose common X1 coordinate is in {1,2,3}. Therefore, the number of internal contacts (face adjacencies), between the boxes that originally composed to Slice11(p) is given by the product 3 · 64 = 192.Computing the number of face adjacencies, perpendicular toX1-axis, between the voxels that originally defined a 3D-OPP now expressed with a 3D-EVM (see text for details).
(a)(b)(c)(d)(e)(f)(g)
π1(S11(p)), Area: 64 u2(h)
π1(S21(p)), Area: 48 u2(i)
Sint=π1(S11(p))∩*π1(S21(p)) Area: 48 u2Now, we proceed to determine the number of internal contacts inSlice21(p). The number of integer coordinates, along X1-axis, between couplets Φ21(p) and Φ31(p) is 3. Such coordinates are 5, 6, and 7. Consider the projection of section S21(p) (Figure 5(h)). The area of  S21(p) is 48 u2. It corresponds to the number of faces embedded in a plane intersecting Slice21(p) which does not coincide with Φ21(p) nor Φ31(p), and whose common X1 coordinate is in {5,6,7}. The number of internal contacts (face adjacencies), between the boxes that originally composed to Slice21(p) is given by the product 3 · 48 = 144. Finally, we compute the regularized intersection between projections of sections S11(p) and S21(p), that is, Sint=π1(S11(p))∩*π1(S21(p)). See Figure 5(i). The area of 2D-OPP Sint is 48 u2. This number corresponds to the number of faces, in the original voxelization, embedded in the supporting plane of couplet Φ21(p). Each one of these faces implies a face adjacency between a voxel that belongs to Slice11(p) and a voxel in Slice21(p). Finally, the number of face adjacencies, perpendicular to X1-axis, between the boxes in p’s original voxelization, is 384. Because of p’s symmetry, it can be easily verified that the number of face adjacencies perpendicular to X2-axis and X3-axis is also 384. Therefore, LC(p)=384+384+384=1,152.As seen, Algorithm4 extracts those sections of nD-OPP p which are perpendicular to XA-axis which implies that it only counts internal contacts perpendicular to this same coordinate axis. Suppose that the coordinates ordering in EVMn(p) is given by X1X2…Xn-1Xn. Each one of the coordinates orderings in the set {X1X2…Xn-1Xn,X2X3…XnX1,X3X4…X1X2,…,XnX1…Xn-2Xn-1} is now used for sorting EVMn(p). Such sorting is performed by calling a procedure SortEVM. Given a permutation Xα1Xα2⋯Xαn, the function sorts the extreme vertices of p first according to coordinate Xα1, after according to coordinate Xα2, and so on until p is sorted according to coordinate Xαn. Next, it is performed a calling to Algorithm 4. By this way, it is computed the number of contacts perpendicular to each one of the axes in nD space. The sum of all contacts perpendicular to all coordinate axes leads to determine LC(p). Algorithm 5 implements this procedure.Algorithm 5:Computing LC(p) for an nD-OPP expressed in the EVM.
Input:AnnD-EVM p and the number n of dimensions.Output: The number of internal contacts, perpendicular to Xi-axis,i=1,2,…,n, between the hypervoxels that originally composed p.ProcedureTotalInternalContacts(EVM p, int n)int Lc = 0foreach sorting in{X1X2…Xn-1Xn,X2X3…XnX1,X3X4…X1X2,…,XnX1…Xn-2Xn-1}  doSortEVM(p, n, sorting)Lc = Lc + InternalContacts(p, n)// Call to Algorithm4.end-of-forreturnLcend-of-procedure


## 5. Representing Color 2D-Animations through 4D-OPPs and the EVM

The procedure described in [10] for processing black and white 2D animations can be directly extended to control colored frames through a 4D-OPP represented through the EVM. This methodology was originally presented in [11, 12]. In Figure 6 an example of a simple color 2D animation composed by four frames whose resolution is 9 × 9 pixels is shown. In each frame can be identified white, red, blue, gray, and cyan regions. We will use this simple animation to exemplify our procedure. We will label each colored frame in the animation as fk  and m will be the number of such frames.Example of a simple color 2D-animation.
(a)(b)(c)(d)A color animation can be handled as a 4D-OPP in the following way [11, 12].(a) The Red-Green-Blue (RGB) components of each pixel will be integrated into a single value. Such value represents the RGB components as an integer with 32 bits. Bits 0–7 correspond to the blue value, bits 8-15 correspond to the green value, bits 16–23 correspond to the red value, and bits 24–31 to thealpha (transparency) value. Each pixel will now be extruded towards the third dimension, where the value integrating its RGB components will now be considered as its X3 coordinate (coordinates X1 and X2 correspond to the original pixels' coordinates). See Figure 7.Figure 7
The 3D space defined for the extrusion of color 2D-pixels.Let us callxfk to the set composed by the rectangular prisms (the extruded pixels) of each extruded frame fk. It is very important to avoid the zero value in the X3 coordinate because a pixel could not be extruded, and therefore its associated prism (a 3D-OPP) will not be obtained. See Figure 8.The sets of prisms resulting of the extrusion of the frames of an animation (presented in Figure6).
(a)(b)(c)(d)(b) Letprismi be a prism in xfk and npr the number of prisms in that set. Due to all the prisms in xfk are quasi disjoint 3D-OPPs, we can easily obtain the final 3D-OPP and its respective 3D-EVM of the whole 3D frame via Corollary 3.26 (all the vertices in a prismi are extreme vertices)(5.1)EVM3(Fk)=⊗i=1nprEVM3(prismi∈xfk),
where Fk is the 3D frame (a 3D-OPP) that represents the union of all the prisms in xfk. See Figure 9.The 3D frames that represent a 2D colored animation (presented in Figure6; Some of their extreme vertices are shown).
(a)(b)(c)(d)(c) Let us extrudeFk into the fourth dimension and thus obtain a 4D hyperprismk whose bases are Fk and its length is proportional to the time fk is to be displayed. The new fourth dimension will measure and represent the time. See Figure 10.Figure 10
The process of extrusion of a 3D frame in order to obtain ahyperprism (some of its extreme vertices are shown).(d) Let p be the 4D-OPP that represents the given color 2D-animation. Polytope p is defined by(5.2)p=⋃k=1mhyperprismk.Due to all them hyperprisms are quasi disjoint 4D-OPPs, then the 4D-EVM for p can be obtained by(5.3)EVM4(p)=⊗k=1mEVM4(hyperprismk).By representing a given color 2D-animation using a 4D-OPP p and its 4D-EVM, we have the following characteristics [11, 12].(i)
The sequence of the projections of sections in p corresponds to the sequence of 3D frames, that is,π4(Sk4(p))=Fk.(ii)
Computation of 3D frames: by Corollary3.23 the 3D-EVM of the frame Fk is computed by EVM3(Fk)=EVM3(Fk-1)⊗EVM3(π4(Φk4(p))).(iii)
Displaying the 2D colored animation: each couplet perpendicular to theX3 axis in each 3D frame Fk contains the polygons to display. The colors to apply to those polygons are referred through the X3 coordinate that contains the integrated RGB components.


## 6. Discrete Compactness of 4D-OPPs: An Application

In this section there will be described our first steps towards an application of Discrete Compactness in a higher dimensional context, via the algorithms presented in Section4, in the classification and indexing of video sequences. In the previous section, it was presented a methodology for representing color 2D animations through 4D-OPPs and the EVM. In the case to be boarded now, we will consider image sequences associated to the Popocatépetl volcano which is located in the Mexican State of Puebla. The images were obtained from the CENAPRED web site [20]. The CENAPRED is a Mexican research center which has as one of its functions monitoring the volcano’s activity.Each sequence presents the volcano’s activity along four consecutive days. The sequences are then composed by 4 images, or frames, each one taken each day. All the images were captured in the time range comprehended from 10 AM to 2 PM We have a set of 521 images which correspond to dates between January 1, 2007 and June 4, 2008. They have resolution 640× 480 under the color model RGB. In a preprocessing phase, images were scaled to the new resolution 320 × 240, and the color model was changed to grayscale. Moreover, a multilevel threshold was applied in order to eliminate noise (specifically we applied some procedures defined in [21]). There were generated 520 sequences to which was applied the procedure described in previous section in such way that for each one was generated its corresponding 4D polytope: two geometrical dimensions (X1 and X2), one color dimension (X3), and one dimension associated to time (X4). Consequently, the obtained 4D polytopes were expressed in the EVM.For each 4D polytope it was computed its Discrete Compactness. It is clear each generated polytope is embedded in a hyper-box with main diagonal defined by the pair of points (0,0,0,0) and (321,241,256,4). Such hyper-box will be calledHmax, and it corresponds to a sequence composed by 4 white frames. On the other hand, let Hmin be the hyper-box described by the main diagonal with start and end points given, respectively, by (0,0,0,0) and (321,241,1,4). It corresponds to a sequence where all the frames are black. The required values LCmax and LCmin are computed through Algorithm 5 by using as input the EVMs associated to hyper-boxes Hmax and Hmin, respectively. That is, LCmax=LC(Hmax) and LCmin=LC(Hmin).The 520 sequences were sorted according to the discrete compactness of their corresponding 4D polytope. Compactness’ maximum obtained value was 0.8367 while the minimum was given by 0.7236. Sequences were grouped in 12 classes (see Tables1 and 2). Each class contains sequences whose discrete compactness is inside an arbitrarily defined range. The classes 1 to 4 group sequences with compactness major or equal to 0.72 and more minor than 0.76. These classes have 1, 3, 1, and 16 members respectively and they have as an interesting characteristic the fact that some of their members are sequences that describe intense volcanic activity. See for example the representative sequences for classes 1, 2, and 3 (Table 1). They describe the same event: an eruption which took place in December 1, 2007 [20].Table 1
Using discrete compactness for classifying 4D-OPPs associated to images sequences (Part 1).
ClassDiscrete compactness rangeRepresentative sequence (arbitrarily choosed)1[0.72, 0.73)2[0.73, 0.74)3[0.74, 0.75)4[0.75, 0.76)5[0.76, 0.77)6[0.77, 0.78)Table 2
Using Discrete Compactness for classifying 4D-OPPs associated to images sequences (Part 2).
ClassDiscrete compactness rangeRepresentative sequence (arbitrarily choosed)7[0.78, 0.79)8[0.79, 0.8)9[0.8, 0.81)10[0.81, 0.82)11[0.82, 0.83)12[0.83, 0.84)Classes 5 to 8 group sequences with discrete compactness inside the range[0.76,0.80). The majority of these sequences describe volcanic activity that goes from null to moderate. The classes 9 to 12 (Table 2) have as members sequences whose 4D polytopes have Discrete Compactness in the range [0.80,0.84). In this case, a great part of these sequences have the property that they correspond to days where the visibility towards the volcano was minimized by clouds or even was null. All the sequences in classes 9, 10, and 11 have cloudy days with low visibility. Moreover, there are also sequences in which the number of days with null visibility oscillated between 1 and 3. Class 12 is the only one where there are sequences such that all four days had null visibility.The above results are promising in the sense that discrete compactness could be applied as a mechanism for indexing/classification/comparison ofn-Dimensional Polytopes. In our example, we have obtained preliminary results that allow classifying 4D objects which in time describe image sequences. We implemented the algorithms and procedures described in this paper in the Java Language (Java Development Kit version 1.6). They were executed in a computer with an Intel Processor Core 2 Duo, 2.40 GHz, and 2 Gigabytes in RAM. In Tables 1 and 2 can be appreciated, for each class, the average processing time required for computing discrete compactness for our 4D polytopes. These time measures provide experimental evidence of efficiency in Discrete Compactness’ computation via the EVM. Another provided data are the referent to the average number of extreme vertices required for representing sequences. A 4D polytope that corresponds to the representation of a sequence of images could be also represented and manipulated via a 4D hypervoxelization. As described previously, all our polytopes are embedded in a 4D hyper-box with main diagonals defined by points (0,0,0,0) and (321,241,256,4). In fact, the required 4D grid for representing our polytopes through a hypervoxelization should be at least of size 320 × 240 × 256 × 4. This implies to store 78,643,200 4D hypervoxels. The average number of extreme vertices, required for representing the sequences contained in class 3, is 388,512. In fact, this is the maximum average from the 12 proposed classes. The ratio (6.1)78,643,200388,512=202.4215
clearly shows how the EVM is effectively a suitable representation for these sequences because its memory requirements are much less when compared with a hypervoxelization scheme.


## 7. Concluding Remarks

Nowadays it is common to find applications where the search of results and properties is more suitable to be performed in hyperspaces. On one side, this implies that the representations to use must be powerful enough in the sense that conciseness, efficiency, and robustness are mandatory characteristics to be taken in account. On the other side, we consider that the notion of Discrete Compactness in higher dimensional contexts plays a fundamental role in tasks related to classification, description, and indexing ofnD polytopes. In such sense, this paper has been devoted to present a set of methodologies that allow the efficient computation of Discrete Compactness of those nD-OPPs whose original representation was based on a hypervoxelization. In Section 3 we described the Extreme Vertices Model in the n-Dimensional space which represents concisely nD-OPPs. It was described a straight method for conversion of hypervoxelizations to the nD-EVM. By expressing a polytope via the EVM, we have, on one hand, the important advantage related to the fact that EVM’s storing requirements are much less than those required by a hypervoxelization model. On the other hand, it is available a set of EVM-based algorithms that allow the manipulation and querying of polytopes represented under our model. As commented in the previous sections, the EVM of a polytope is in fact a subset of its vertices. However, the algorithms presented in Section 3 obtain, from such subset of vertices, useful topological and geometrical information. Supported in those algorithms, we have proposed, specifically in Section 4, methodologies for performing the computation of Discrete Compactness. We have extended, in direct way, concepts presented by Bribiesca in [1, 5], in order to apply them on nD-OPPs expressed under the EVM.In Section6 we presented how by using our EVM-based implementation of Discrete Compactness it was possible to classify in efficient way images sequences associated to Popocatépetl volcano. They were grouped according to the value of their corresponding compactness. Informally, we saw how sequences with visual common properties have near compactness values. On the other hand, currently we are working in procedures for extracting the number of kD elements on the boundary, k=0,1,2,…,n-1, of an nD-OPP expressed in the EVM. Such counts by themselves are geometrical factors describing the polytope, but they can also be useful for determining, for example, topological factors such as the well-known Euler characteristic. The first steps presented in this paper, the obtained results and observations, and the new methodologies we are defining for extracting another geometrical and topological factors, encourage us to concentrate our efforts towards the following main idea. we want to determine how factors, such as Discrete Compactness, Euler characteristic, boundary elements counts, and so forth, that describe a higher dimensional polytope representing a sequence, can be used for a specification for indexing and classification of video sequences. Moreover, we will investigate if such factors, that provide us descriptive information about a higher dimensional object, can be used to infer properties and relations about the events taking place in the video sequences under consideration. The nD-EVM will play a paramount role because it is expected to take full advantage of its storage requirements and its algorithms’ efficiency.Finally, we conclude by commenting thenD-EVM is a model that has been successfully applied in tasks such as (1) image comparison by enhanced image-based reasoning, (2) collision detection of 2D and 3D objects whose trajectories are, respectively, modeled as 3D and 4D-OPPs, (3) concise representation and efficient querying of volume datasets, (4) morphological operations on binary images, and (5) connected components labeling. Applications 1, 2, and 3 are appropriately developed in [11] while applications 4 and 5 are presented in [22, 23]. In [9–11, 23] there are described algorithms based on the nD-EVM, besides the ones described in this paper, which are useful and efficient for performing other interrogations and manipulations on nD-OPPs.



---

*Source: 598910-2010-09-07.xml*