Entity-oriented spatial coding scheme and its application for spatial topology

ABSTRACT

Based on a newly proposed spatial data model Spatial Chromatic Model (SCM), we developed a spatial coding scheme, called the full-coded Ordinary Arranged Chromatic Diagram (full-OACD). As a type of spatial tessellation, full-OACD partitions a geographic space into a number of subspaces, such as cells, edges, and vertices. These subspaces are called spatial particles and are assigned with unique codes chromatic codes. The generation, structure, computation, and properties of full-OACD are introduced. Relations between particulate chromatic codes and spatial topology are investigated. Full-OACD is a kind of new discrete spatial coordinate system where the information of real-world entities is embedded. Full-OACD provides an informative and meaningful spatial coding framework for spatial topological analysis and many other potential applications in geospatial information science.

KEYWORDS:

• Spatial data model
• spatial coding
• spatial tessellation
• spatial topology

1. Coding the geographical space

To make fast computation and effective expression, spatial information and other non-spatial attributes of geo-entities are usually coded, exchanged, and interpreted in various forms of digits, strings, symbols, or even two-dimensional barcodes. In fact, the well-known Cartesian coordinates used in GIS is a coding system – points in it are assigned coordinates (x, y, z) as codes to mark their spatial locations. A global coordinate system provides a coding scheme using pairs of codes (longitudes and latitudes) to represent geographical entities or regions (Longley et al. 2001; Frank, and Robinson 2010). The spatial index assigns codes (indices) to spatial objects so that they can be rapidly retrieved from spatial databases (Feitosa et al. 2007; Halaoui 2008). In geocoding systems, zip codes allow places and postal addresses to be readily recalled and exclusively identified (Curry 1998; Roongpiboonsopit, and Karimi 2010).

The object we try to code in this study is the space itself. Coding any geographical entity is not too difficult since entities are usually countable, so a simple way is assigning them indices or names. However, indexing entities is a rather arbitrary method indices or names help differentiate one entity from the other, but they generally contain no further information, so besides her/his name, a person may also have an ID number containing more information about her/his gender, birthday, and birthplace. In comparison, it may not be easy to code space because space is typically uncountable. How to code space depends on how we treat it. If we treat space as being continuous, then the traditional Cartesian coordinates in mathematics and vector data models in computer science are used to code space. To deal with the continuous space more simply and faster, we can also treat space being discrete, and hence the well-known raster data model is used for picture representation and image processing (Fischer and Wang 2011). With respect to an origin (0, 0), a two-dimensional vector point is coded by two real numbers (x, y), while a raster point (pixel) is coded by two integers (i, j). Once a Cartesian coordinate system has been established, no matter it is coded in integer or real number, it is right there, being independent of the entities of interest, playing a background and waiting for entity living, as a container in Newtonian absolute space. If we put an entity in the container, it immediately gains its spatial information, coded by a group of organized points or pixels. In this way, spatial information is transferred from background space to entities, and after that, spatial relations between entities can be further analyzed and deduced. If we do not put any entity in the container, then it is empty, just like we always start with an empty map or blank canvas as we open a cartographic or painting software, for example, ArcGIS or Adobe illustrator.

The purpose of this study is not to replace or discard those traditional coding systems based on point-set topology, Cartesian coordinates, vector, and raster data models. Instead, the purpose is to create a new spatial coordinate system. In the new system, spatial coordinates (codes) are with respect to their generators (entities), differing from those traditional origin-based coordinates. In other words, the new coordinate system is based on an entity-oriented spatial coding scheme, and via this scheme, spatial information is transferred from entities to spaces, rather than from spaces to entities that occurred in Cartesian systems. Therefore, the basic principle of the new system is entity first. If without any entity, any background space is meaningless. The relativity principle in physics indicates that if all matter disappears, then the Newtonian absolute space is also non-exist, as Penrose (2004) has stated “physics should be defined entirely in terms of the relation of one body to another, and that the very notion of a background space should be abandoned”. Similarly, as a contemporary of Newton, Leibniz has claimed his relative space theory that ‘space is only the system of entity relations’ (Loemker 1989).

The new entity-oriented spatial coding system, called full-coded ordinary arranged chromatic diagram (full-OACD), is based on a newly proposed spatial data model – Spatial Chromatic Model (SCM) (Zhu 2015). Spaces in SCM are made by entities and coded by their relations, and therefore, they are not absolute backgrounds but relative spaces depending on the entities who made them. SCM has demonstrated many theoretical advantages and potential applications in computer and information science, such as spatial tessellation, topological relation, and point pattern recognition (Zhu, and Yu 2010; Zhu 2015). The standard model of SCM is called the Ordinary Arranged Chromatic Diagram (OACD) (Zhu, and Yu 2010). The full-OACD proposed in this study is a type of extension of OACD. Some spaces (the bisectors) in OACDs are not coded, but in full-OACD, the full space was all coded, meaning it does not contain spatial gaps where the chromatic codes are missing. The spaces in both OACDs and full-OACDs are labeled by the chromatic codes, that is, their spatial coordinates, which can be treated as a kind of arrangement or order of the entities who made the spaces. The father of cybernetics, Norbert Wiener, had an insightful thought on the arrangement and order of the objects – ‘One of the most interesting aspects of the world is that it can be considered to be made up of patterns. A pattern is essentially an arrangement. It is characterized by the order of the elements of which it is made rather than by the intrinsic nature of these elements’ (Haken 2006).

In this study, we primarily focus on using full-OACDs to explore spatial topological relations. The traditional spatial topology in GIS, such as the 9-I model, is usually based on Cartesian coordinates and point-set topology, which involves lots of floating-number computations (Egenhofer, and Franzosa 1991; Egenhofer, and Herring 1991; Clementini, Sharma, and Egenhofer 1994; Shen, Chen, and Liu 2018; Worboys, and Duckham 2021). For example, to obtain spatial topological relation between two polygons P1 and P2 with node coordinates (3.24, 5.35, 6.61, 7.87, 1.23) and (3.25, 6.12, 4.43, 5.20), we have to execute complicated algorithms to build their boundaries, interiors, exteriors, and then infer their topological relations by judging conditions such as whether a node locates in the interior of a polygon or two edges are partially overlapped. Comparably, topological relations between chromatic spaces in full-OACDs can be easily computed by just using the chromatic codes of cells or clusters, which only involves simple algorithms based on integral computations since chromatic codes are always integers or half-integers. The computation of the topological relations among geographical entities can be obtained as an extension of the technique proposed in this study and is an interesting problem to address in future work.

The below sections will introduce, analyze, and discuss the procedures of generating full-OACDs, some important definitions, notations, properties, and theorems (Section 2), topological relations among cells, edges, vertices, and complexes (Section 3), and their spatial entity representation, data structure, notes, potential applications for GIS, and suggested future work (Section 3).

2. Full-Coded ordinary arranged chromatic diagram

As mentioned in the above section, SCM must be based on some real or abstract discrete objects. Let E{e₁, e₂, … , e_n} be an entity set containing n entities. The entity set is also called the generator set and entities in E are generators, which can be treated as any general objects. The set Q(e_i) is a subset of E × E consisting of all ordered entity-pairs in which the first entities are e_i while the second entities are not e_i, that is, Q(e_i) = {(e_i,e_j)|e_i,e_j ∈ E, j ≠ i}.

Definition 1.

Given a point p in m-dimensional Euclidean space R^m and an ordered entity-pair (e_i, e_j), the encoding function t(p, (e_i, e_j)) is defined by

(1) $\mathit{t}\left(\mathit{p},\left(e_i,e_j\right)\right)=\left\{\begin{array}{c}0,\mathit{d}\left(\mathit{p},e_i\right)>\mathit{d}\left(\mathit{p},e_j\right)\\ 1,\mathit{d}\left(\mathit{p},e_i\right)<\mathit{d}\left(\mathit{p},e_j\right)\\ \frac{1}{2},\mathit{d}\left(\mathit{p},e_i\right)=\mathit{d}\left(\mathit{p},e_j\right)\end{array}\right.$(1)

where d(p, e) is a type of distance metric, for example, the Euclidean distance between p and e. Then, t(p, Q(e_i)) is defined by

(2) $\mathit{t}\left(\mathit{p},\mathit{Q}\left(e_i,e_j\right)\right)={\sum }_{\mathit{q}\in \mathit{Q}\left(e_i\right)}\mathit{t}\left(\mathit{p},\mathit{q}\right)$(2)

Definition 2.

The chromatic code of a point p in a space R^m, with respect to the entity set E, is defined by

(3) $(\mathit{t}(\mathit{p},\mathbf{Q}(\mathit{e}1)),\mathit{t}(\mathit{p},\mathbf{Q}(\mathit{e}2)),\dots ,\mathit{t}(\mathit{p},\mathbf{Q}(\mathit{ei})),\dots ,\mathit{t}(\mathit{p},\mathbf{Q}(\mathit{en})))$(3)

Points in R^m with the same chromatic codes are merged into the same subspaces and hence form a type of spatial tessellation, called Full-coded Ordinary Arranged Diagram (full-OACD). A full-OACD in R^m space and generated from n entities is denoted by fOACD(n, R^m). This study mainly focuses on planar full-OACDs in R² with Euclidean distance metric d(p, e). Figure 1 shows the simplest fOACD(2, R²), generated from two entities Blue (B) and Green (G). With respect to entity-pairs (B, G) and (G, B), points p in the plane are merged into three subspaces where t(p, (B, G)) or t(p, (G, B)) equal 1, 0, and $\frac{1}{2}$, respectively, see Figure 1(a,b). Then, the chromatic codes of each subspaces are (t(p, (B, G)), t(p, (G, B)), i.e. (1, 0), (0, 1), and $\left(\frac{1}{2},\frac{1}{2}\right)$ in Figure 1c. Note that in Equation (1)(1) $\mathit{t}\left(\mathit{p},\left(e_i,e_j\right)\right)=\left\{\begin{array}{c}0,\mathit{d}\left(\mathit{p},e_i\right)>\mathit{d}\left(\mathit{p},e_j\right)\\ 1,\mathit{d}\left(\mathit{p},e_i\right)<\mathit{d}\left(\mathit{p},e_j\right)\\ \frac{1}{2},\mathit{d}\left(\mathit{p},e_i\right)=\mathit{d}\left(\mathit{p},e_j\right)\end{array}\right.$(1) if we do not set $\mathit{t}\left(\mathit{p},(e_i,e_j\right))=\frac{1}{2}$ when d(p, e_i) = d(p, e_j), that is, in Figure 1, the bisectors were not coded by $\left(\frac{1}{2},\frac{1}{2}\right)$, then the full-OACD turns to be the original OACD introduced in (Zhu, and Yu 2010).

Figure 1. A full-OACD generated from 2 entities.

An alternative way to generate full-OACDs is using a half-plane or half-space partition. It follows the below four steps.

Step (1): Let Q be a family of subsets of E consisting of all unordered entity-pairs {e_i,e_j} in E. With respect to an entity-pair q = {e_i, e_j}∈ Q, using their perpendicular bisector pb<i, j> to partition the space into two half-planes hp(i, j) and hp(j, i), where a point p in hp(i, j) is with Euclidean distance d(p, e_i) <d(p, e_j), in hp(j, i) with d(p, e_j) <d(p, e_i), and in pb<i, j> with d(p, e_i) = d(p, e_j).

Step (2): Assign two half-planes hp(i, j) and hp(j, i) the codes (e₁⁰, e₂⁰, …, e_i¹, …, e_n⁰) and (e₁⁰, e₂⁰, …, e_j¹, …, e_n⁰), respectively, in which the subscript number is the index of each entity, and the superscript number is an assigned numerical variable t(q). In this step, only for entities e_i or e_j, t(q) = 1, but for the others, t(q) = 0. Particularly, the bisector pb<i, j> is assigned the code $\left(e_1^0,e_2^0,\dots ,e_i^{\frac{1}{2}},\dots ,e_j^{\frac{1}{2}},\dots ,e_n^0\right)$, that is, for both e_i and e_j, t(q) = $\frac{1}{2}$, but for the others, t(q) = 0.

Step (3): Repeat steps (1) and (2) for all $\mathit{k}=\frac{1}{2}\mathit{n}\left(\mathit{n}-1\right)$ entity-pairs in Q, and then overlay the 2k half-planes so that they generate a spatial tessellation containing a number of subspaces that could be geometrical faces, edges, and vertices.

Step (4): The chromatic code of each subspace is the sum of the values t(q) assigned by each half-plane partition, that is,

(4) $\left(p_1^{{\sum }_{\mathit{q}\in \mathbf{Q}}\mathit{t}\left(\mathit{q}\right)},p_2^{{\sum }_{\mathit{q}\in \mathbf{Q}}\mathit{t}\left(\mathit{q}\right)},\dots ,p_i^{{\sum }_{\mathit{q}\in \mathbf{Q}}\mathit{t}\left(\mathit{q}\right)},\dots ,p_n^{{\sum }_{\mathit{q}\in \mathbf{Q}}\mathit{t}\left(\mathit{q}\right)}\right)$(4)

Figure 2 shows the procedure of generating an fOACD(3, R²). By half-plane partitions, we get six half-planes (Figure 2(b–d)), then we overlap them together into a diagram (Figure 2e), and finally, we sum their t(q)’s to generate the chromatic code for each subspace in the diagram (Figure 2F).

Figure 2. The procedure of generating a full-OACD(3, R²). (a) the generator set consists of three points marked with color R, G, and B; (b)-(d) Half-plane partitions and assignments of chromatic codes with respect to perpendicular bisectors pb<b, G>, pb<g, R>, and pb<r, B>, respectively. (e) Overlapping all the six half-planes in (b)-(d) together; and (f) Adding all chromatic components together to form the chromatic codes.

Subspaces (e.g. faces, edges, vertices, etc.) generated in a full-OACD are called spatial particles (denoted by Ω), and faces are particularly called cells (denoted by ζ), which was originally introduced in OACDs (Zhu, and Yu 2010; Zhu 2015). Chromatic codes of spatial particles are n-tuples such as (t₁, t₂, … , t_i, … , t_n), in which the number t_i is called chromatic component of the entity e_i, or chromatic component at location e_i. Easy to know that t_i will be either integer or half-integer.

Sometimes, if we only have interest in, say, components at e_i and e_j, then a chromatic code (t₁, t₂, … , t_i, … , t_j, … , t_n) can be rewritten in a short form such as (t_i, t_j)∪(T_others), or just (t_i, t_j).

Figure 3 shows two full-OACD examples. Figure 3a is a complete fOACD(4, R²) and Figure 3b is a homomorphic part of an fOACD(6, R²), where each spatial particle is coded in 6-tuples. Note that in Figure 3b we are only interested in the generated spatial tessellation itself, so the locations of six generators do not matter and hence are omitted.

Figure 3. Two examples of full-OACDs. (a) a full-OACD(4, R²); (b) the homomorphic part of a full-OACD(6, R²).

Examining spatial particulate patterns and chromatic codes in full-OACDs such as Figure 3, we can dig out many interesting properties and spatial relations among particles and their codes.

Definition 3.

Given a particle Ω(t₁, t₂, … , t_n), the ascending order of its chromatic components is called the chromatic base of the particle and denoted by β(Ω) = {t’1, t’2, … , t’n}.

For example, cells ζ₁(0, 2, 3, 1) and ζ₂(2, 1, 3, 0) both have the same chromatic base β(ζ₁) = β(ζ₂) = {0, 1, 2, 3}. If two components are equal, then their orders are randomly assigned, for example, the bases of edges $\left\{\frac{3}{2},0,3,\frac{3}{2}\right\}$ and $\left\{\frac{3}{2},\frac{3}{2},3,0\right\}$ are both $\left\{0,\frac{3}{2},\frac{3}{2},3\right\}$.

Chromatic codes are always the permutations of different chromatic bases. In previous studies, the chromatic base was also called the primary code of a cell (Zhu, and Yu 2010).

Definition 4.

If two particles Ω₁(t₁₁, t₁₂, … , t_1i, … , t_1n) and Ω₂(t₂₁, t₂₂, … , t_2i, … , t_2n) have the same chromatic codes, then they are called equi-color, and denoted by Ω₁ = Ω₂, that is,

(5) $\mathrm{\forall i},t_{1\mathit{i}}=t_{2\mathit{i}}\iff {\mathrm{\Omega }}_1={\mathrm{\Omega }}_2$(5)

otherwise, Ω₁ ≠ Ω₂.

If they have the same chromatic bases, then they are called equi-base, denoted by Ω₁ ≅ Ω₂, that is, if β(Ω₁) = {t’₁₁, t’₁₂, … , t’_1i, … ,t’_1n} and β(Ω₂) = {t’₂₁, t’₂₂, … , t’_2i, … ,t’_2n}, then

(6) $\mathrm{\forall i},\mathit{t}{ }_{1i}^{\prime }=\mathit{t}{ }_{2i}^{\prime }\iff {\mathrm{\Omega }}_1\cong {\mathrm{\Omega }}_2$(6)

otherwise, ${\mathrm{\Omega }}_1\mathit{/}\cong {\mathrm{\Omega }}_2$.

Property 1. Given two particles Ω₁and Ω₂, it is east to know that

(7) ${\mathrm{\Omega }}_1={\mathrm{\Omega }}_2\iff {\mathrm{\Omega }}_1\cong {\mathrm{\Omega }}_2$(7)

and hence

(8) ${\mathrm{\Omega }}_1\mathit{/}\cong {\mathrm{\Omega }}_2\iff {\mathrm{\Omega }}_1\ne {\mathrm{\Omega }}_2$(8)

This property indicates that if two cells are equi-color, they must be equi-base, and if they are not equi-base, they are impossible to be equi-color.

The number of cells, edges, and vertices in an fOACD(n, R²) depends on the spatial entity pattern of the generator set E. Entities in the real world can be with any shape and size, but in this study, we only treat them as points, so that an entity set could be equivalent to a point set. We focus mainly on the general cases of a point set E in a plane: (1) no more than two bisectors are parallel, and (2) no more than three bisectors are concurrent, except that they are generated by the three point-pairs, which make a triangle.

Definition 5. In a general case of point set E, any three point-pairs from three different points generate a vertex, called the 3-I vertex (i.e. the intersection of three perpendicular bisectors of a triangle, namely, the triangle’s circumcenter), denoted by φ^3I, and any two point-pairs from four different points generate a vertex, called the 2-I vertex (i.e. the intersection of two perpendicular bisectors), denoted by φ^2I.

Therefore, vertices (denoted by φ) in a general case of fOACD(n, R²) are either 2-I or 3-I, see their examples in Figure 3.

Property 2. An fOACD(n, R²) contains ${\sum }_{i=1}^{C_2^n}\mathit{i}-C_3^n+1$cells, $(C_2^n{)}^2-3C_3^n$edges, $C_3^n$3-I vertices, and$\frac{1}{2}{C}_2^n{C}_2^{n-2}$2-I vertices.

Proof.

The proof of the cell number could be referred to (Zhu, and Yu 2010). Here, we only prove the edge number. Suppose in a plane there are n lines that intersect with each other, then each line is divided into n edges by the other n – 1 lines, therefore the n lines will generate n² edges. The total n point will generate C_n² lines (bisectors) and hence (C_n²)² edges. But every three points generate a vertex that will reduce to 3 edges, therefore the total edge number will be (C_n²)² − 3C_n³.

This property tells that given n generators, how many cells, edges, 2-I, and 3-I vertices will be generated.

Property 3. In an fOACD(n), the chromatic base of cells is always

(9) $\mathbf{N}=\mathit{\hspace{0.17em}}\left\{0,\mathit{\hspace{0.17em}}1.,\mathit{n}\mathit{\hspace{0.17em}}-1\right\}$(9)

This property has been proven by (Zhu, and Yu 2010). It implies that all cells are equi-base, and any two components in a cellular code are not equal. Below we use N[i, j] to denote the integer set between i and j (including i and j).

Property 4. In an fOACD(n), the chromatic bases of edges are

(10) $\left\{\mathbf{N}\mathrm{\setminus }\left\{\mathit{z},\mathit{z}+1\right\},\mathit{z}+\frac{1}{2},\mathit{z}+\frac{1}{2}\right\}$(10)

for any z ∈ N[0, n – 2], meaning for each z from 0 to n – 2, we obtain a base in which z and z +1 were removed from N and two $\left(\mathit{z}+\frac{1}{2}\right)$’s were moved in.

Particularly, an edge (denoted by η) generated by bisector pb<i, j> bears a code

(11) $\mathit{\eta }\left(x_i^{z+\frac{1}{2}},x_j^{z+\frac{1}{2}}\right)$(11)

for z ∈ N[0, n – 2].

Proof.

Suppose η is the edge between two cells ζ₁ and ζ₂, therefore before the partition of pb<i, j>, ζ₁ and ζ₂ should be merged into a larger cell with code (x^z_i, x^z_j), that is, point i and j have the same component z. After the partition, ζ₁ and ζ₂’s codes will be $\left(x_i^{z+1},x_j^z\right)$ and $\left(x_i^z,x_j^{z+1}\right)$, see the proof of Lemma 2 in (Zhu, and Yu 2010). With respect to all other bisectors pb<i, x> or pb<j, x>, x ∈ I\{i, j}, if has not gained any components, then the minimum of z could be 0; if always gained one component for all the other n – 2 bisectors, then the maximum of z could be n – 2. Therefore, η’s chromatic code will be $\left(x_i^{z+\frac{1}{2}},x_j^{z+\frac{1}{2}}\right)$, and their bases will be $\left\{\mathbf{N}\mathrm{\setminus }\left\{\mathit{z},\mathit{z}+1\right\},\mathit{z}+\frac{1}{2},\mathit{z}+\frac{1}{2}\right\}$, for z ∈ N[0, n – 2].

Property 5. The chromatic bases of 2-I vertices are

(12) $\left\{\mathbf{N}\mathrm{\setminus }\{z_1,z_2,z_1+1,z_2+1\right\},z_1+\frac{1}{2},z_1+\frac{1}{2},z_2+\frac{1}{2},z_2+\frac{1}{2}\}$(12)

for any z₁ ∈ N[0, n – 4] and z₂ ∈ N[z₁ +2, n – 2]. Particularly, a vertex φ^2I generated by two bisectors pb<i, j> and pb<u, v> bears a code

(13) ${\phi }^{2\mathit{I}}\left(x_i^{z_1+\frac{1}{2}},x_j^{z_1+\frac{1}{2}},x_u^{z_2+\frac{1}{2}},x_v^{z_2+\frac{1}{2}},\right)$(13)

or

(14) ${\phi }^{2\mathit{I}}\left(x_i^{z_2+\frac{1}{2}},x_j^{z_2+\frac{1}{2}},x_u^{z_1+\frac{1}{2}},x_v^{z_1+\frac{1}{2}},\right)$(14)

for any z₁ ∈ N[0, n – 4] and z₂ ∈ N[z₁ +2, n – 2].

Proof.

Suppose pb<i, j> and pb<u, v> are the last two bisectors partitioning a merged cell, then according to the Lemma 2 in (Zhu, and Yu 2010), before the two partitions, the cell should be with a code such as $\left(x_i^{z_1},x_j^{z_1},x_u^{z_2},x_v^{z_2}\right)$. Let z₁ is the smaller integer, and then z₂ = z₁ + Δ. After the two partitions by pb<i, j> and pb<u, v>, four new cells will be generated with codes

(15) $\left(x_i^{z_1},x_j^{z_1+1},x_u^{z_1+\mathrm{\Delta }+1},x_v^{z_1+\mathrm{\Delta }}\right)$(15)

(16) $\left(x_i^{z_1+1},x_j^{z_1},x_u^{z_1+\mathrm{\Delta }+1},x_v^{z_1+\mathrm{\Delta }}\right)$(16)

(17) $\left(x_i^{z_1},x_j^{z_1+1},x_u^{z_1+\mathrm{\Delta }},x_v^{z_1+\mathrm{\Delta }+1}\right)$(17)

(18) $\left(x_i^{z_1+1},x_j^{z_1},x_u^{z_1+\mathrm{\Delta }},x_v^{z_1+\mathrm{\Delta }+1}\right)$(18)

If Δ = 0 or 1, then we can always find that in some codes of Equations (15)(15) $\left(x_i^{z_1},x_j^{z_1+1},x_u^{z_1+\mathrm{\Delta }+1},x_v^{z_1+\mathrm{\Delta }}\right)$(15) –(18(18) $\left(x_i^{z_1+1},x_j^{z_1},x_u^{z_1+\mathrm{\Delta }},x_v^{z_1+\mathrm{\Delta }+1}\right)$(18) ) two components are equal. For example, if Δ = 0 , there are two z₁’s and two z₁ + 1’s in Equation (15)(15) $\left(x_i^{z_1},x_j^{z_1+1},x_u^{z_1+\mathrm{\Delta }+1},x_v^{z_1+\mathrm{\Delta }}\right)$(15) , and if Δ = 1 , there are two z₁ + 1’s in Equation (16)(16) $\left(x_i^{z_1+1},x_j^{z_1},x_u^{z_1+\mathrm{\Delta }+1},x_v^{z_1+\mathrm{\Delta }}\right)$(16) . But the cellular base is N, meaning any two components are not equal, therefore Δ ≥ 2. Because pb<i, j> and pb<u, v> involve four entities, then the maximum of z₁ should be n – 4, and hence z₁ = N[0, n – 4], z₂ = N[z₁ +2, n – 2]. The remainder of the proof follows along the line of the proof of Property 4.

Property 6. The chromatic bases of 3-I vertices are

(19) $\{\mathbf{N}\mathrm{\setminus }\left\{\mathit{z},\mathit{z}+1,\mathit{z}+2\right\},\mathit{z}+1,\mathit{z}+1,\mathit{z}+1\}$(19)

for any z ∈ N[0, n – 3]. Particularly, a vertex φ^3I generated by three bisectors pb<i, j>, pb<j, k>, and pb<k, i> bears a code

(20) ${\phi }^{3\mathit{I}}\left(x_i^{z+1},x_j^{z+1},x_k^{z+1}\right)$(20)

for any z ∈ N[0, n – 3].

Proof.

Suppose before the partitions of pb<i, j>, pb<j, k>, and pb<k, i>, the merged cell has a code $\left(x_i^z,x_j^{\mathit{z}+{\mathrm{\Delta }}_1},x_k^{\mathit{z}+{\mathrm{\Delta }}_2}\right)$, where Δ₁ ≥0 and Δ₂ ≥0. After the partitions, six new cells will be generated with codes

(21) $\left(x_i^{z+2},x_j^{\mathit{z}+{\mathrm{\Delta }}_1+1},x_k^{\mathit{z}+{\mathrm{\Delta }}_2}\right)\cup \left(X_{\mathit{others}}\right)$(21)

(22) $\left(x_i^{z+2},x_j^{\mathit{z}+{\mathrm{\Delta }}_1},x_k^{\mathit{z}+{\mathrm{\Delta }}_{2+1}}\right)\cup \left(X_{\mathit{others}}\right)$(22)

(23) $\left(x_i^{z+1},x_j^{\mathit{z}+{\mathrm{\Delta }}_1},x_k^{\mathit{z}+{\mathrm{\Delta }}_2+2}\right)\cup \left(X_{\mathit{others}}\right)$(23)

(24) $\left(x_i^{z+1},x_j^{\mathit{z}+{\mathrm{\Delta }}_1+2},x_k^{\mathit{z}+{\mathrm{\Delta }}_2}\right)\cup \left(X_{\mathit{others}}\right)$(24)

(25) $\left(x_i^z,x_j^{\mathit{z}+{\mathrm{\Delta }}_1+1},x_k^{\mathit{z}+{\mathrm{\Delta }}_2+2}\right)\cup \left(X_{\mathit{others}}\right)$(25)

(26) $\left(x_i^z,x_j^{\mathit{z}+{\mathrm{\Delta }}_1+2},x_k^{\mathit{z}+{\mathrm{\Delta }}_2+1}\right)\cup \left(X_{\mathit{others}}\right)$(26)

We examine the below possible values ofΔ₁ and Δ₂.

(1) Δ₁ = 1 or Δ₁ = 2, Δ₂ = 1 or Δ₂ = 2.

If Δ₁ = 1 or Δ₁ = 2, for example, in Equations (23)(23) $\left(x_i^{z+1},x_j^{\mathit{z}+{\mathrm{\Delta }}_1},x_k^{\mathit{z}+{\mathrm{\Delta }}_2+2}\right)\cup \left(X_{\mathit{others}}\right)$(23) and (22(22) $\left(x_i^{z+2},x_j^{\mathit{z}+{\mathrm{\Delta }}_1},x_k^{\mathit{z}+{\mathrm{\Delta }}_{2+1}}\right)\cup \left(X_{\mathit{others}}\right)$(22) ) there will be two components equaling z + 1 or z + 2; similarly, if Δ₂ = 1 or Δ₂ = 2, in Equations (24)(24) $\left(x_i^{z+1},x_j^{\mathit{z}+{\mathrm{\Delta }}_1+2},x_k^{\mathit{z}+{\mathrm{\Delta }}_2}\right)\cup \left(X_{\mathit{others}}\right)$(24) and (21(21) $\left(x_i^{z+2},x_j^{\mathit{z}+{\mathrm{\Delta }}_1+1},x_k^{\mathit{z}+{\mathrm{\Delta }}_2}\right)\cup \left(X_{\mathit{others}}\right)$(21) ) there will be two components equaling z + 1 or z + 2.

(2) Δ₁ ≥3, Δ₂ ≥3.

According to Equations (25)(25) $\left(x_i^z,x_j^{\mathit{z}+{\mathrm{\Delta }}_1+1},x_k^{\mathit{z}+{\mathrm{\Delta }}_2+2}\right)\cup \left(X_{\mathit{others}}\right)$(25) and (26(26) $\left(x_i^z,x_j^{\mathit{z}+{\mathrm{\Delta }}_1+2},x_k^{\mathit{z}+{\mathrm{\Delta }}_2+1}\right)\cup \left(X_{\mathit{others}}\right)$(26) ), there must be values z + 1 and z + 2 in X_others, because they are not in locations x_i, x_j, or x_k. However, according to Equations (21)(21) $\left(x_i^{z+2},x_j^{\mathit{z}+{\mathrm{\Delta }}_1+1},x_k^{\mathit{z}+{\mathrm{\Delta }}_2}\right)\cup \left(X_{\mathit{others}}\right)$(21) –(24(24) $\left(x_i^{z+1},x_j^{\mathit{z}+{\mathrm{\Delta }}_1+2},x_k^{\mathit{z}+{\mathrm{\Delta }}_2}\right)\cup \left(X_{\mathit{others}}\right)$(24) ), z + 1 and z + 2 are already in x_i, so that they cannot be in X_others.

From the above two cases, we know that the only allowed values of Δ₁ and Δ₂ are both 0, and the merged cell must bear a code

(27) $\left(x_i^z,x_j^z,x_k^z\right)$(27)

Then at the intersection of the three bisectors, the 3-I vertex acquires components $\frac{1}{2}$ at x_i and $\frac{1}{2}$ at x_j from pb<i, j>, $\frac{1}{2}$ at x_j and $\frac{1}{2}$ at x_k from pb<j, k>, $\frac{1}{2}$ at x_k and $\frac{1}{2}$ at x_i from pb<k, i>, and therefore gain a code

(28) $\left(x_i^{z+\frac{1}{2}+\frac{1}{2}},x_j^{z+\frac{1}{2}+\frac{1}{2}},x_k^{z+\frac{1}{2}+\frac{1}{2}}\right)=\left(x_i^{z+1},x_j^{z+1},x_k^{z+1}\right)$(28)

From Equations (21)(21) $\left(x_i^{z+2},x_j^{\mathit{z}+{\mathrm{\Delta }}_1+1},x_k^{\mathit{z}+{\mathrm{\Delta }}_2}\right)\cup \left(X_{\mathit{others}}\right)$(21) –(26(26) $\left(x_i^z,x_j^{\mathit{z}+{\mathrm{\Delta }}_1+2},x_k^{\mathit{z}+{\mathrm{\Delta }}_2+1}\right)\cup \left(X_{\mathit{others}}\right)$(26) ), we know that X_others do not contain components z, z + 1, and z + 2, thus we know the base of the 3-I vertex is in form of Equation (19)(19) $\{\mathbf{N}\mathrm{\setminus }\left\{\mathit{z},\mathit{z}+1,\mathit{z}+2\right\},\mathit{z}+1,\mathit{z}+1,\mathit{z}+1\}$(19) . Because the range of z in a cell is from 0 to n – 1, the minimum z should be 0 and maximum z should be z + 2 = n – 1 ⇒ z = n – 3.

This property indicates that the chromatic codes of 3-I vertices contain three equal integers that are different from the rest integers in the codes. If cancel one z + 1, Equation (19)(19) $\{\mathbf{N}\mathrm{\setminus }\left\{\mathit{z},\mathit{z}+1,\mathit{z}+2\right\},\mathit{z}+1,\mathit{z}+1,\mathit{z}+1\}$(19) can be rewritten as

(29) $\{\mathbf{N}\mathrm{\setminus }\left\{\mathit{z},\mathit{z}+2\right\},\mathit{z}+1,\mathit{z}+1\}$(29)

for any z ∈ N[0, n – 3].

Theorem 1.

Different types of particles in a full-OACD are not equi-base, that is,

(30) $\mathit{\zeta }\mathit{/}\cong \mathit{\eta }\mathit{/}\cong {\phi }^{2\mathit{I}}\mathit{/}\cong {\phi }^{3\mathit{I}}$(30)

This theorem provides an approach to determine particle types. For example, if we see a particle with chromatic components being all unequal integers, then it must be a cell; if it contains only two half-integers, it must be an edge; if it contains three equal integers, it must be a 3-I vertex; and if it contains four half-integers, it must be a 2-I vertex.

Notation 1.

The component-counting function H(Ω, m) is a function counting the number of m in Ω’s chromatic code, that is, this function tells how many components in Ω are equal to an integer m.

For example, given Ω = (2, 4, 2, 0, 2, 5) and m = 2, then H(Ω, m) = 3 because there are three components being 2.

Definition 6.

The difference tuple of two particles Ω₁(t₁₁, t₁₂, … , t_1n) and Ω₂(t₂₁, t₂₂, … , t_2n) is defined by

(31) $\begin{array}{c}\mathrm{\Psi }\left({\mathrm{\Omega }}_1,{\mathrm{\Omega }}_2\right)=\left({\psi }_1,{\psi }_2,\dots ,{\psi }_n\right)\\ =\left(\left|t_{11}-t_{21}\right|,\left|t_{12}-t_{22}\right|,\dots ,\left|t_{1\mathit{n}}-t_{2\mathit{n}}\right|\right)\end{array}$(31)

where ${\psi }_i=\left|t_{1\mathit{i}}-t_{2\mathit{i}}\right|$.

Then the chromatic distance between the two particles is defined by

(32) $\mathit{\delta }\left({\mathrm{\Omega }}_1,{\mathrm{\Omega }}_2\right)={\sum }_{i=1}^n{\psi }_i$(32)

and each ψ_i is called the chromatic distance at the component or location i, and denoted by δ(ψ_i).

In addition, the code distance between two particles is defined by

(33) $\mathit{\gamma }\left({\mathrm{\Omega }}_1,{\mathrm{\Omega }}_2\right)=\mathit{n}-\mathit{H}\left(\mathrm{\Psi }\left({\mathrm{\Omega }}_1,{\mathrm{\Omega }}_2\right),0\right)$(33)

Chromatic distance is also called transition number T between two cells in our previous studies, and it is equal to the Manhattan distance between two particles. The code distance is equal to the Hamming distance between two particles if we treat their chromatic codes and components as strings rather than numbers. For example, the chromatic distance between two cells Ω₁(0, 3, 2, 1) and Ω₂(1, 3, 2, 0) is |0 – 1| + |3 – 3| + |2 – 2| + |1 – 0| = 2, and their code distance is also 2 because their first and last two components are different.

Definition 7.

The union of m particles Ω₁(t₁₁, t₁₂, … , t_1n), Ω₂(t₂₁, t₂₂, … , t_2n), … , Ω_m(t_m1, t_m2, … , t_mn) is called a complex or m-complex (denoted by Θ), and its code is given by

(34) $\begin{array}{c}\mathrm{\Theta }\left({\mathrm{\Omega }}_1,{\mathrm{\Omega }}_2,\dots ,{\mathrm{\Omega }}_m\right)={\sum }_{i=1}^m{\mathrm{\Omega }}_m\\ =\left({\sum }_{i=1}^m{t}_{\mathit{i}1},{\sum }_{i=1}^m{t}_{\mathit{i}2},\dots ,{\sum }_{i=1}^m{t}_{\mathit{in}}\right).\end{array}$(34)

The m particles are called the elemental particles of the m-complex. If the m particles are all cells, then the m-complex is also called an m-cell cluster (denoted by ξ). A particle itself could be taken as a 1-complex.

The chromatic code of a complex is the respective summations of the codes of its component particles. For example, particles Ω₁(0, 3, 2, 1) and Ω₂(1, 3, 2, 0) compose a complex Θ₁(Ω₁, Ω₂) with the chromatic code (1, 6, 4, 1) which is calculated from Ω1 + Ω₂ = (0 + 1, 3 + 3, 2 + 2, 1 + 0).

Theorem 2.

If ζ₁ and ζ₂ are two cells in a full-OACD, then

(35) ${\zeta }_1\ne {\zeta }_2$(35)

This theorem has been proven by (Zhu, and Yu 2010). It tells that any two cells are not equi-color. Their codes are unique.

Because any vertex in full-OACD is either 2-I or 3-I, a full-OACD is therefore tessellated by two types of structural units shown in Figure 4: one unit containing φ^2I is called 2-I unit (Figure 4a), and the other unit containing φ^3I is called 3-I unit (Figure 4b). Note that the “I” in 2-I/3-I vertices or 2-I/3-I units stands for ‘intersection’, meaning that the vertices or units are made by the intersections of 2 or 3 perpendicular bisectors.

Figure 4. Two basic structural units of full-OACD. (a) 2-I unit; (b) 3-I unit.

According to the proofs of Property 5 and 6 (Zhu 2016), particulate codes in 2-I/3-I units should be those shown in Figure 4, and then it is easy to calculate and prove the below properties.

Property 7. A 2-I unit generated by bisectors pb<i, j> and pb<u, v> contains the following nine particles.

(1) One 2-I vertex with a code

(36) ${\phi }_{\mathrm{ijuv}}^{2I}\left(x_i+\frac{1}{2},x_j+\frac{1}{2},x_u+\frac{1}{2},x_v+\frac{1}{2}\right)$(36)

(2) Four edges with codes

(37) $\begin{array}{c}{\eta }_{\mathit{iju}}\left(x_i+\frac{1}{2},x_j+\frac{1}{2},x_u+1,x_v\right),{\eta }_{\mathit{ijv}}\left(x_i+\frac{1}{2},x_j+\frac{1}{2},x_u,x_v+1\right)\\ {\eta }_{\mathit{uvi}}\left(x_i+1,x_j,x_u+\frac{1}{2},x_v+\frac{1}{2}\right),{\eta }_{\mathit{uvj}}\left(x_i,x_j+1,x_u+\frac{1}{2},x_v+\frac{1}{2}\right)\end{array}$(37)

(3) Four cells with codes

(38) $\begin{array}{c}{\zeta }_{\mathit{iu}}\left(x_i+1,x_j,x_u+1,x_v\right),{\zeta }_{\mathit{iv}}\left(x_i+1,x_j,x_u,x_v+1\right)\\ {\zeta }_{\mathit{ju}}\left(x_i,x_j+1,x_u+1,x_v\right),{\zeta }_{\mathit{jv}}\left(x_i,x_j+1,x_u,x_v+1\right)\end{array}$(38)

Property 8. A 3-I unit generated by bisectors pb<i, j>, pb<j, k> and pb<k, i> contains the following 13 particles.

(1) One 3-I vertex with a code

(39) ${\phi }_{ijk}^{3I}\left(x_i+1,x_j+1,x_k+1\right)$(39)

(2) Six edges with codes

(40) $\begin{array}{c}{\eta }_{\underset{\_}{\mathit{jk}}\mathit{i}}\left(x_i,x_j+\frac{3}{2},x_k+\frac{3}{2}\right),{\eta }_{\mathit{i}\underset{\_}{\mathit{jk}}}\left(x_i+2,x_j+\frac{1}{2},x_k+\frac{1}{2}\right)\\ {\eta }_{\underset{\_}{\mathit{ki}}\mathit{j}}\left(x_i+\frac{3}{2},x_j,x_k+\frac{3}{2}\right),{\eta }_{\mathit{j}\underset{\_}{\mathit{ki}}}\left(x_i+\frac{1}{2},x_j+2,x_k+\frac{1}{2}\right)\\ {\eta }_{\underset{\_}{\mathit{ij}}\mathit{k}}\left(x_i+\frac{3}{2},x_j+\frac{3}{2},x_k\right),{\eta }_{\mathit{k}\underset{\_}{\mathit{ij}}}\left(x_i+\frac{1}{2},x_j+\frac{1}{2},x_k+2\right)\end{array}$(40)

Note, in Equation (40)(40) $\begin{array}{c}{\eta }_{\underset{\_}{\mathit{jk}}\mathit{i}}\left(x_i,x_j+\frac{3}{2},x_k+\frac{3}{2}\right),{\eta }_{\mathit{i}\underset{\_}{\mathit{jk}}}\left(x_i+2,x_j+\frac{1}{2},x_k+\frac{1}{2}\right)\\ {\eta }_{\underset{\_}{\mathit{ki}}\mathit{j}}\left(x_i+\frac{3}{2},x_j,x_k+\frac{3}{2}\right),{\eta }_{\mathit{j}\underset{\_}{\mathit{ki}}}\left(x_i+\frac{1}{2},x_j+2,x_k+\frac{1}{2}\right)\\ {\eta }_{\underset{\_}{\mathit{ij}}\mathit{k}}\left(x_i+\frac{3}{2},x_j+\frac{3}{2},x_k\right),{\eta }_{\mathit{k}\underset{\_}{\mathit{ij}}}\left(x_i+\frac{1}{2},x_j+\frac{1}{2},x_k+2\right)\end{array}$(40) , the underlined index indicates the perpendicular bisector which makes the edge.

(3) Six cells with codes

(41) $\begin{array}{c}{\zeta }_{\mathit{ijk}}\left(x_i+2,x_j+1,x_k\right),{\zeta }_{\mathit{ikj}}\left(x_i+2,x_j,x_k+1\right)\\ {\zeta }_{\mathit{jik}}\left(x_i+1,x_j+2,x_k\right),{\zeta }_{\mathit{jki}}\left(x_i,x_j+2,x_k+1\right)\\ {\zeta }_{\mathit{kij}}\left(x_i+1,x_j,x_k+2\right),{\zeta }_{\mathit{kji}}\left(x_i,x_j+1,x_k+2\right)\end{array}$(41)

The spatial relations among particles in 2-I/3-I units have three types: adjacent, interval, and opposite, see Figure 5. If spatial relations between two particles in 2I/3-I units are different, their chromatic and code distances are also different, see Property 9.

Figure 5. Three types of particle relations in 2-I/3-I units: adjacent (Adj.), interval (Int.) and opposite (Opp.).

Property 9. Within a 2-I or 3-I unit of an fOACD (n, R²), the chromatic distance and code distance between two particles Ω₁ and Ω₂ are listed in Table 1.

Table 1. Chromatic and code distances between two particles in 2-I/3-I units.

			2-I Units			3-I Units
Ω1	Ω2	Relation	δ	γ	Base	δ	γ	Base
Vertex φ	Edge η	Adjacent	1	2	$\mathit{/}\cong$	2	3	$\mathit{/}\cong$
Vertex φ	Cell ζ	Adjacent	2	4	$\mathit{/}\cong$	2	2	$\mathit{/}\cong$
Edge η1	Edge η2	Adjacent	2	4	$\mathit{/}\cong$	2	3	$\mathit{/}\cong$
Edge η1	Edge η2	Opposite	2	2	$\cong$	4	3	$\mathit{/}\cong$
Edge η1	Edge η2	Interval	n/a	n/a	n/a	3	2	$\cong$
Edge η	Cell ζ	Adjacent	1	2	$\mathit{/}\cong$	1	2	$\mathit{/}\cong$
Edge η	Cell ζ	Opposite	3	4	$\mathit{/}\cong$	4	3	$\mathit{/}\cong$
Edge η	Cell ζ	Interval	n/a	n/a	n/a	3	3	$\mathit{/}\cong$
Cell ζ1	Cell ζ2	Adjacent	2	2	$\cong$	2	2	$\cong$
Cell ζ1	Cell ζ2	Opposite	4	4	$\cong$	4	2	$\cong$
Cell ζ1	Cell ζ2	Interval	n/a	n/a	n/a	4	3	$\cong$

Note: The spatial relations listed in this table are shown in Figure 7.

A very important property of full-OACDs is that we expect their particulate codes to be unique.

Theorem 3.

If η₁ and η₂ are two edges in a full-OACD, then

(42) ${\eta }_1\ne {\eta }_2$(42)

Proof.

Suppose ζ1Left and ζ1Right are two cells beside η1, and ζ2Left and ζ2Right are two cells beside η₂, and then they make two 2-cell clusters ξ₁(ζ_1Left, ζ_1Right) and ξ₂(ζ_2Left, ζ_2Right), respectively. It has been proved that chromatic codes of any connected 2-cell cluster are unique (Zhu 2015), that is, ξ₁ ≠ ξ2. Then, according to the Property 9.2 in (Zhu 2016), ${\eta }_1=\frac{1}{2}{\xi }_1\ne \frac{1}{2}{\xi }_2={\eta }_2$.

This theorem tells that chromatic codes of edges are unique.

Theorem 4.

If φ₁ and φ₂ are two vertices in a full-OACD, then

(43) ${\phi }_1\ne {\phi }_2$(43)

Proof.

Case (1): One vertex is 2-I and the other vertex is 3-I.

According to Property 1, ${\phi }^{2\mathit{I}}\mathit{/}\cong {\phi }^{3\mathit{I}}$, so ${\phi }_1\ne {\phi }_2$.

Case (2): They are both 3-I vertices.

Suppose φ^3I₁ and φ^3I₂ are different 3-I vertices but with the same code (x^z_i, x^z_j, x^z_k), i.e. they have three chromatic components which are the same integer z given by three points i, j, and k. However, the bisectors generated from 3 points can only intersect at one 3-I vertex, so if φ₁ and φ₂ are different vertices, their codes are impossible to be the same, i.e. ${\phi }_1^{3I}\ne {\phi }_2^{3I}$.

(3) They are both 2-I vertices.

Suppose φ^2I₁ and φ^2I₂ are two different 2-I vertices. The φ^2I₁ was generated by pb<i₁, j₁> and pb<u₁, v₁>, and hence with a code $\left(x_{i_1}^{z_1},x_{j_1}^{z_1},x_{u_1}^{z_2},x_{v_1}^{z_2}\right)$; The φ^2I₂ was generated by pb<i₂, j₂> and pb<u₂, v₂>, and hence with a code $\left(x_{i_2}^{z_1},x_{j_2}^{z_1},x_{u_2}^{z_2},x_{v_2}^{z_2}\right)$.

The only way to make φ^2I₁ = φ^2I₂ is that i₁ = i₂, j₁ = j₂, u₁ = u₂, and v₁ = v₂, but this makes φ^2I₁ and φ^2I₂ are the same vertices because two bisectors can only intersect at one 2-I vertex. Therefore, if φ^2I₁ and φ^2I₂ are two different 2-I vertices, their codes are impossible to be equal.

Based on the above three cases, we know that ${\phi }_1\ne {\phi }_2$.

This theorem indicates that chromatic codes of vertices are also unique. Ultimately, according to Theorems 1–4, we obtain the below corollary.

Corollary 1.

Chromatic codes of spatial particles in a full-OACD are all unique, that is, given two particles Ω₁, Ω₂ ∈ fOACD(n, R²),

(44) ${\mathrm{\Omega }}_1\ne {\mathrm{\Omega }}_2$(44)

3. Spatial particle topology in full-OACD

A planar full-OACD contains three types of particles: vertices, edges, and cells. Spatial topological relations among these particles are usually similar to those conventional relations for vectorial geometry in spatial information theory, such as the equal, adjacent, disjoint, and overlap. Figure 6 shows the spatial relations between two particles investigated in this study, and these relations can be simply represented and calculated by using chromatic codes. In addition, the more complicated spatial relations among m-complexes can be also reasoned by analyzing their chromatic codes. In sections 3 and 4, we will demonstrate the spatial topological relations between two particles or complexes, and we will also demonstrate how to present and reason their spatial topological relations by using their chromatic codes. We particularly focus on cells and clusters. Property 9 (Table 1) already gives the conditions from which we know that different particulate spatial relations correspond to different chromatic and code distances, however, those are only necessary conditions. In this section, we will give proofs that those conditions are also sufficient so that we can use two distances δ(Ω₁, Ω₂), γ(Ω₁, Ω₂) and their bases β(Ω₁), β(Ω₂) to determine their topological spatial relations.

Figure 6. General spatial topological relations among particles in full-OACDs.

3.1. Spatial topology between particles

There are six types of spatial combinations for particles: vertex–vertex (V–V), vertex–edge (V–E), vertex–cell (V–C), edge–edge (E–E), edge–cell (E–C), and cell–cell (C–C), and their relations are typically equal, joint, disjoint, and others, see examples in Figure 6. These particle–particle relations also underlie the further topological analysis of complexes.

3.1.1. Vertex-Vertex (V-V) relations

In terms of theorem 4, V–V relations between φ₁ and φ₂ are quite simple either equal, that is, ∩(φ₁, φ₂) = φ₁, or disjoint, that is, ∩(φ₁, φ₂) = Ø, see Figure 6a.

Proposition 1.

If φ₁ and φ₂ are two vertices, then

(45) $\begin{array}{c}\cap \left({\phi }_1,{\phi }_2\right)={\phi }_1\iff {\phi }_1={\phi }_2\\ \cap \left({\phi }_1,{\phi }_2\right)=\mathrm{\varnothing }\iff {\phi }_1\ne {\phi }_2\end{array}$(45)

Because we have proved that chromatic codes are unique in a full-OACD, the “equal” relation, i.e. two particles completely overlap, is easy to determine that the two particles are topologically equal, if and only if they are equal in codes, that is, Ω₁ equals Ω₂ ⇔ Ω1 = Ω₂, namely, δ(Ω₁, Ω₂) = 0. Note, because a full-OACD is a type of spatial tessellation, meaning it contains neither gaps nor overlaps, therefore topologically, it does not contain any two equal particles.

3.1.2. Vertex-Edge (V-E) relations

Typically an edge contains two ends, and hence a V-E relation is like that a vertex is one of the ends of the edge (Figure 6d), that is, ∩(η, φ) = φ; otherwise they are disjoint, that is, ∩(η, φ) = Ø (Figure 6F).

Proposition 2.

Given an edge η and a vertex φ,

(46) $\cap \left(\mathit{\eta },\mathit{\phi }\right)=\mathit{\phi }\iff \mathit{\delta }\left(\mathit{\eta },\mathit{\phi }\right)\le 2\cap \left(\mathit{\eta },\mathit{\phi }\right)=\varnothing \iff \mathit{\delta }\left(\mathit{\eta },\mathit{\phi }\right)2$(46)

Note that proofs of this proposition and some other below propositions are too long, so we put them in a preprint article (Zhu 2016).

Given an edge η, a useful function is to calculate all possible chromatic codes of vertices contained in the edge, that is, determining the boundaries of the edge. Function ∂η returns all contained vertices, and in particular, ∂(η, 2I) and ∂(η, 3I) return all 2-I and 3-I vertices, respectively.

Notation 2.

The procedure of ∂(η, 2I):

Let η be an edge with code $\left(x_i^{z+\frac{1}{2}},x_j^{z+\frac{1}{2}}\right){\cup }^{\left({\mathit{X}}_{\mathit{others}}\right)}$, where X_others = N\{z, z + 1}. (1) Find the minimum component w in X_others, assume it is x^w_u, (2) Find w + 1: if found, assume it is x^w+1_v, then change x^w_u and x^w+1_vboth to w + $\frac{1}{2}$to form a 2-I vertex $\left(x_i^{z+\frac{1}{2}},x_j^{z+\frac{1}{2}},x_u^{w+\frac{1}{2}},x_v^{w+\frac{1}{2}}\right)$, if not found, let w = w + 1 and repeat (1) and (2) until w = n – 2.

Because (X_others) can be partitioned into two parts N1 = N[0, z – 1] and N2 = N[z + 2, n – 1], if z ≠ 0 and z ≠ n – 2, given any component pair such as $\left(x_u^w,x_v^{w+1}\right)$ in N1 or N2, it produces an edge with codes $\left(x_i^{z+\frac{1}{2}},x_j^{z+\frac{1}{2}},x_u^{w+\frac{1}{2}},x_v^{w+\frac{1}{2}}\right)$. Because there are z – 1 such component pairs in N1, and n – z – 3 pairs in N2, therefore in total we have n – 4 available pairs. If z ≠ 0 and z ≠ n – 2, then either N1 or N2 will be empty and the other will contain n – 3 available pairs. For example, for edge $\left(0,\frac{7}{2},5,1,2,\frac{7}{2}\right)$ with z = 3 (see edge 07A247 in Figure 3b), it has n – 4 = 2 available component pairs. We first found (0, 1) and next (1, 2), and then they produce two 2-I vertices $\left(\frac{1}{2},\frac{7}{2},5,\frac{1}{2},2,\frac{7}{2}\right)$ (see vertex 17A147 in Figure 3b) and $\left(0,\frac{7}{2},5,\frac{3}{2},\frac{3}{2},\frac{7}{2}\right)$, respectively.

Notation 3.

The procedure of ∂(η, 3I):

Let η be an edge with code $\left(x_i^{z+\frac{1}{2}},x_j^{z+\frac{1}{2}}\right){\cup }^{\left({\mathit{X}}_{\mathit{others}}\right)}$, where X_others = N\{z, z + 1}. (1) Find the minimum component w in (X_others), assume it is x^w_k, (2) If e = (2z + 1 + w) ≡ 0(mod3) and e ∉ (X_others), then change $x_i^{z+\frac{1}{2}}$, $x_j^{z+\frac{1}{2}}$, and x^w_kto $\frac{e}{3}$to produce a 3-I vertex $(x_i^{\frac{e}{3}},x_j^{\frac{e}{3}},x_k^{\frac{e}{3}})$, (3) Let w = w + 1 and repeat (2) until w = n – 1.

Because e ≡ 0(mod3) and z = N[0, n – 2], therefore w = 3m – 2z – 1, with conditions that w = N[0, n – 1]\{z, z + 1} and $\mathit{m}\in \mathbf{N}\left[1,\frac{2}{3}\left(\mathit{n}+1\right)\right]$. For example, for the edge $\left(2,3,\frac{9}{2},0,1,\frac{9}{2}\right)$ with z = 4 (edge 469,029 in Figure 3b), only in conditions m = 4 and w = 3 the edge can produce a 3-I vertex (2, 4, 4, 0, 1, 4) (see vertex 488,028 in Figure 3b).

Therefore, spatial relations between a vertex φ and an edge η can be also determined by checking whether φ ∈ ∂η.

Another V-E relation is that two vertices are exactly the two ends of an edge, called they are segmented (Figure 6e), that is, ∩(η, φ₁, φ₂) = {φ₁, φ₂}. This relation is equivalent to two vertices sharing an edge.

Proposition 3.

Given an edge η and two vertices φ₁ and φ₂, which could be both 2-I, or 3-I, or one is 2-I and the other is 3-I, then

(47) $\cap \left(\mathit{\eta },{\phi }_1^{2I},{\phi }_2^{2I}\right)=\left\{{\phi }_1^{2I},{\phi }_2^{2I}\right\}\iff \mathit{\delta }\left({\phi }_1^{2I},{\phi }_2^{2I}\right)=2$(47)

(48) $\cap \left(\mathit{\eta },{\phi }_1^{2I},{\phi }_2^{3I}\right)=\left\{{\phi }_1^{2I},{\phi }_2^{3I}\right\}\iff \mathit{\delta }\left({\phi }_1^{2I},{\phi }_2^{3I}\right)=3$(48)

(49) $\cap \left(\mathit{\eta },{\phi }_1^{3I},{\phi }_2^{3I}\right)=\left\{{\phi }_1^{3I},{\phi }_2^{3I}\right\}\iff \mathit{\delta }\left({\phi }_1^{3I},{\phi }_2^{3I}\right)=4$(49)

Above we proved that if the chromatic distance between two 2-I vertices is 2, then they must be segmented with an edge. The other two cases Equations (48)(48) $\cap \left(\mathit{\eta },{\phi }_1^{2I},{\phi }_2^{3I}\right)=\left\{{\phi }_1^{2I},{\phi }_2^{3I}\right\}\iff \mathit{\delta }\left({\phi }_1^{2I},{\phi }_2^{3I}\right)=3$(48) and (49(49) $\cap \left(\mathit{\eta },{\phi }_1^{3I},{\phi }_2^{3I}\right)=\left\{{\phi }_1^{3I},{\phi }_2^{3I}\right\}\iff \mathit{\delta }\left({\phi }_1^{3I},{\phi }_2^{3I}\right)=4$(49) ) can be proved in the same way, but the proofs are too long to be presented here.

Similarly, we can also use the ∂ function to determine whether two vertices and one edge are segmented, that is,

(50) $\cap \left(\mathit{\eta },{\phi }_1,{\phi }_2\right)=\left\{{\phi }_1,{\phi }_2\right\}\iff {\phi }_1,{\phi }_2\in \mathrm{\partial \eta }$(50)

3.1.3. Vertex-Cell (V-C) relations

The relation between a vertex φ and a cell ζ is that φ is one of edge ends, and the edge is one of the boundaries of the cell. This relation is called the cell ζ containing the vertex φ, that is, ∩(ζ, φ) = φ (Figure 6b); otherwise, they are disjoint, that is, ∩(ζ, φ) = Ø (Figure 6c).

Proposition 4.

Given a vertex φ and a cell ζ, then

(51) $\cap \left(\mathit{\zeta },\mathit{\phi }\right)=\mathit{\phi }\iff \mathit{\delta }\left(\mathit{\zeta },\mathit{\phi }\right)=2\cap \left(\mathit{\zeta },\mathit{\phi }\right)=\varnothing \iff \mathit{\delta }\left(\mathit{\zeta },\mathit{\phi }\right)2$(51)

3.1.4. Edge-Edge (E-E) relations

In 2-I and 3-I units, there are three types of relations between two edges: adjacent, opposite, and interval and their chromatic distances could be 2, 3, and 4, respectively. The three relations are all topologically the same as two edges sharing either 2-I or 3-I vertices as their common ends. In this EE relation, the two edges are called joint with a vertex, that is, ∩(η₁, η₂) = φ. The E–E joint relation has further two types: collinear (denoted by $\overline{{\eta }_1{\eta }_2}$, see Figure 6g) and noncollinear (Figure 6h). If two edges do not share any particles, they are disjoint (Figure 6i). The E–E collinear relation is easy to determine by using the below proposition.

Proposition 5. Given two edges ${\eta }_1\left(x_i^{z_1+\frac{1}{2}},x_j^{z_1+\frac{1}{2}}\right)$and ${\eta }_2\left(x_u^{z_1+\frac{1}{2}},x_v^{z_1+\frac{1}{2}}\right)$,

(52) $\overline{{\eta }_1{\eta }_2}\iff \mathit{i}=\mathit{u},\mathit{j}=\mathit{v}$(52)

Note that Proposition 5 only tells whether two edges are collinear, but two collinear edges may not be always joint. A feasible method to reason topological joint between two edges is using ∂η to calculate all possible vertices contained by the two edges, and if among them two vertices are equal, then the edges are joint with this vertex. This method, however, can only tell if two edges are possible to be joint, but in real full-OACDs, they may not be joint because the joint vertex is hidden in higher dimensional spaces. For example, the edges (36A038) and (25A058) in Figure 3b both have an end vertex (44A048) and hence are joint, but the vertex does not emerge in the R² plane so that the two edges appear to be disjoint. Similarly, if we only use chromatic distances listed in Table 1 to determine E–E relations, then they may also lead to mistakes in R² plane due to the same reason. For the same example, in Figure 3b, δ((36A038), (25A058)) = 2, γ((36A038), (25A058)) = 3, indicating they are joint with a 3-I vertex, that is, the resultant (44A048) of ∂η, but in the given plane they are not joint. Therefore, the below proposition is only true for fOACD at R^{n − 1} space, where all theoretically allowed edges, cells, and vertices are not hidden.

Proposition 6.

Given two edges η₁ and η₂ in fOACD(n, R^{n − 1}), let (δ, γ) = (δ(η₁, η₂), γ(η₁, η₂)), then

(53) $\cap \left({\eta }_1,{\eta }_2\right)=\mathit{\phi }\iff \left\{\begin{array}{c}{\phi }^{2\mathit{I}}\iff \left(\mathit{\delta },\mathit{\gamma }\right)=\left(2,2\right)\vee \left(2,4\right)\mathit{\hspace{0.17em}}\\ {\phi }^{3\mathit{I}}\iff \left(\mathit{\delta },\mathit{\gamma }\right)=\left(2,3\right)\vee \left(3,2\right)\vee \left(4,3\right)\end{array}\right.$(53)

If we do not care about the types of the joint vertex, then we can integrate conditions in Table 1 to

(54) $\cap \left({\eta }_1,{\eta }_2\right)=\mathit{\phi }\iff \left\{\begin{array}{c}\mathit{\delta }\le 3\mathit{\hspace{0.17em}}\\ \left(\mathit{\delta },\mathit{\gamma }\right)=\left(4,3\right),{\eta }_1\mathit{/}\cong {\eta }_2\end{array}\right.$(54)

3.1.5. Edge-Cell (E-C) relations

There are three types of relations between an edge and a cell: (1) contain: the edge is a boundary of the cell, i.e. ∩(ζ, η) = η (Figure 6j), (2) joint: the cell shares a vertex with the edge, that is, ∩(ζ, η) = φ (Figure 6k), and (3) disjoint: they do not share any particles, that is, ∩(ζ, η) = Ø (Figure 6l).

Proposition 7.

Given a cell ζ and an edge η, then

(55) $\cap \left(\mathit{\zeta },\mathit{\eta }\right)=\mathit{\eta }\iff \mathit{\delta }\left(\mathit{\zeta },\mathit{\eta }\right)=1$(55)

Similar to the function ∂η, a function ∂ζ is used for calculating all edges bounding a cell.

Notation 4. The procedure of ∂ζ:

Let ζ be a cell with the base N[0, n – 1]. (1) Find the minimum component z in its code, assume it is x_i^z, (2) Find z +1, assume it is x_j^z+1, then change x_i^zand x_j^z+1 to $x_i^{z+\frac{1}{2}}$and $x_j^{z+\frac{1}{2}}$, respectively. (3) Let z = z + 1 and repeat (1) and (2) until z = n – 2.

Therefore, in theory, each cell should be bounded by n – 1 edges, that is, they are n-hedras, but in fact, many cells are triangles, quadrilaterals, or polygons with edges much less than n – 1, indicating that a large number of edges are hidden.

Proposition 8.

Given a cell ζ and an edge η in an fOACD(n, R^{n − 1}), then

(56) $\cap \left(\mathit{\zeta },\mathit{\eta }\right)=\mathit{\phi }\iff 3\le \mathit{\delta }\left(\mathit{\zeta },\mathit{\eta }\right)\le 4$(56)

According to the above two propositions, the disjoint E-C relation can be determined by the below corollary.

Corollary 2.

Given a cell ζ and an edge η, then

(57) $\cap \left(\mathit{\zeta },\mathit{\eta }\right)=\mathrm{\varnothing }\iff \mathit{\delta }\left(\mathit{\zeta },\mathit{\eta }\right)>4$(57)

We can use ∂ζ and then ∂η function, that is, ∂(∂ζ), to obtain all vertices contained by a cell. Also, we can define a new function ∂²ζ to directly find out all those vertices, using similar procedures in ∂η. Therefore, using functions ∂ζ and ∂²ζ , E-C relations are also expressed by

(58) $\cap \left(\mathit{\zeta },\right)=\mathit{\eta }\iff \mathit{\eta }\in \partial \mathit{\zeta }\cap \left(\mathit{\zeta },\right)=\mathit{\phi }\iff \mathit{\eta }\notin \partial \mathit{\zeta }\wedge {\partial }^2\mathit{\zeta }\cap \partial \mathit{\eta }\ne \varnothing \cap \left(\mathit{\zeta },\right)=\varnothing \iff {\partial }^2\mathit{\zeta }\cap \partial \mathit{\eta }=\varnothing$(58)

Note that because some joint vertices may be hidden in high-dimensional spaces, therefore some joint E-C relations may appear to be disjoint in R² plane.

3.1.6. Cell-Cell (C-C) relations

The C–C relations have three types: (1) connected: two cells share a common edge, that is, ∩(ζ₁, ζ₂) = η (Figure 6m), (2) joint: they share a common vertex, that is, ∩(ζ₁, ζ₂) = φ (Figure 6n), and (3) disjoint: they do not share any particles, that is, ∩(ζ₁, ζ₂) = Ø (Figure 6o). The connected and joint relations correspond to the five C–C relations that occurred in 2-I or 3-I units (Table 1), that is, the adjacent corresponds to the connected, and the opposite and interval correspond both to the joint.

Proposition 9.

Given two cells ζ₁ and ζ₂,

(59) $\cap \left({\zeta }_1,{\zeta }_2\right)=\mathit{\eta }\iff \mathit{\delta }\left({\zeta }_1,{\zeta }_2\right)=2$(59)

Proposition 10.

Given two cells ζ₁ and ζ₂,

(60) $\cap \left({\zeta }_1,{\zeta }_2\right)=\mathit{\phi }\iff \mathit{\delta }\left({\zeta }_1,{\zeta }_2\right)=4$(60)

Another approach to reason C–C relations is using ∂ζ to calculate all edges of two cells, and if among them the two edges are equal, then the two cells must be connected. We can also use ∂²ζ to calculate all vertices contained by two cells, and if among them two vertices are equal, then the two cells are joint. Still, some connected edges and joint vertices may be hidden in higher dimensional spaces.

3.2. Spatial topology between complexes

The space in a full-OACD may contain a large number of spatial particles, and these particles may regroup and transform into an even larger number of spatial complexes. Topological relations and computations among complexes are hence much more complicated than those among particles. As the union set of particles, a complex may contain different types of particles, for example, containing two cells, two edges, and three vertices, such complexes are called mixed complexes; or it contains only a single type of particles, for example, containing cells only, such complexes are called uniform complexes. In addition, there are also two information scenarios: for a given complex, (1) we know its code as well as all elemental particles, and (2) we only know its code but do not know its elemental particles. This section demonstrates a tentative study of spatial complex topology, particularly focusing on the most important uniform complex cluster, with the scenario that we know all elemental cells.

3.2.1. Spatial connectivity of a cluster

Spatial connectivity is an important issue for analyzing complexes and clusters. In a general sense, the connectivity of clusters in full-OACD is similar to those in graph theory, complex network, algebraic geometry, and point-set topology. A disconnected cluster is usually treated as many connected clusters rather than a single cluster.

Let us define the connectivity of a cluster. If a cluster contains two cells ζ₁ and ζ₂ and they are connected as shown in Proposition 9, namely, δ(ζ₁, ζ₂) = 2, then there is a path linking them, denoted by ρ(ζ₁, ζ₂). If a cluster contains three cells ζ₁, ζ₂, and ζ₃, and there is a path ρ(ζ₁, ζ₂), and another path ρ(ζ₂, ζ₃), then we define a path ρ(ζ₁, ζ₃) between ζ₁ and ζ₃, and call them path-connected by the path-cell ζ₂, that is, ρ(ζ₁, ζ₃) = (ζ₂). Similarly, any two cells are path-connected if they are linked by a series of intermediate path-cells.

Definition 8. Given a cluster ξ{ζ₁, ζ₂, … , ζ_n}, it is connected if it meets two conditions: (1) any two cells are path-connected, and (2) all path-cells are the elemental cells of the cluster.

Notation 5.

The function Conn(ξ) returns ξ’s connectivity. It can be carried out by steps (1) select any one cell from ξ as the seed of the connected set C_c and the other cells remain as the waiting-list set C_w, (2) search cells in C_w to find out the cell ζ_w which is connected to any cell ζ_c in C_c, that is, δ(ζ_c, ζ_w) = 2. (3) If ζ_w is found, then move it from C_w to C_c, and repeat step (2) until C_w is empty, and then Conn(ξ) returns 1, meaning is connected, If ζ_w is not found, then Conn(ξ) returns 0, meaning is disconnected.

3.2.2. Types and reasoning of cluster-cluster topological relations

Given two clusters ξ₁ and ξ₂, their cluster–cluster (Cs–Cs) topological relations, such as equal, contain, touch, and overlap, are demonstrated in Figure 7. Because clusters are the union set of cells and if their elemental cells are known, for instance, ξ₁ = {ζ₁₁, ζ₁₂, … , ζ_1n} and ξ₂ = {ζ₂₁, ζ₂₂, … , ζ_2m}, then some of Cs–Cs relations are easy to know by using the below set operations.

(61) ${\xi }_1\text{equals}{\xi }_2\iff {\xi }_1\cap {\xi }_2={\xi }_1={\xi }_2{\xi }_1\text{contains}{\xi }_2\iff {\xi }_1\supset {\xi }_2{\xi }_1\text{disjoint}{\xi }_2\iff {\xi }_1\cap {\xi }_2=\varnothing {\xi }_1\text{overlaps}{\xi }_2\iff {\xi }_1\cap {\xi }_2\ne \varnothing \ne {\xi }_1\ne {\xi }_2$(61)

Figure 7. Six types of complex topological relations in full-OACDs.

Another topological relation between two clusters is adjacency (Figure 7d), which can be determined by

(62) ${\xi }_1\mathrm{touches}{\xi }_2\iff {\xi }_1\cap {\xi }_2=\mathrm{\varnothing }\wedge \mathit{Conn}\left({\xi }_1\cup {\xi }_2\right)=1$(62)

Or we can use ∂ζ and ∂²ζ functions to compare their edges and vertices, that is,

(63) ${\xi }_1\text{touches}{\xi }_2\iff {\xi }_1\cap {\xi }_2=\varnothing \wedge \partial {\xi }_1\cap \partial {\xi }_2\ne \varnothing {\xi }_1\text{joints}{\xi }_2\iff \partial {\xi }_1\cap \partial {\xi }_2=\varnothing \wedge {\partial }^2{\xi }_1\cap {\partial }^2{\xi }_2\ne \varnothing$(63)

where $\mathrm{\partial }\mathit{\xi }=\underset{\mathit{\zeta }\in \mathit{\xi }}{\cup }\mathrm{\partial \zeta }$ and ${\mathrm{\partial }}^2\mathit{\xi }=\underset{\mathit{\zeta }\in \mathit{\xi }}{\cup }{\mathrm{\partial }}^2\mathit{\zeta }$.

A more comprehensive method to explore Cs–Cs relations is examining C–C relations for all elemental cells. Given two complexes Θ₁(Ω₁₁, Ω₁₂, … , Ω_1n) and Θ₂(Ω₂₁, Ω₂₂, … , Ω_2m), their chromatic-distance matrix is defined by dM(Θ₁, Θ₂) = [δ_ij]_n×m, where δ_ij = δ(Ω_1i, Ω_2j), that is,

(64) $\mathit{dM}\left({\mathrm{\Theta }}_1,{\mathrm{\Theta }}_2\right)=\left[\begin{array}{ccc}\begin{array}{cc}\mathit{\delta }\left({\mathrm{\Omega }}_{11},{\mathrm{\Omega }}_{21}\right)& \mathit{\delta }\left({\mathrm{\Omega }}_{11},{\mathrm{\Omega }}_{22}\right)\\ \mathit{\delta }\left({\mathrm{\Omega }}_{12},{\mathrm{\Omega }}_{21}\right)& \mathit{\delta }\left({\mathrm{\Omega }}_{12},{\mathrm{\Omega }}_{22}\right)\end{array}& \cdots & \begin{array}{c}\mathit{\delta }\left({\mathrm{\Omega }}_{11},{\mathrm{\Omega }}_{2\mathit{m}}\right)\\ \mathit{\delta }\left({\mathrm{\Omega }}_{12},{\mathrm{\Omega }}_{2\mathit{m}}\right)\end{array}\\ ⋮& \ddots & ⋮\\ \begin{array}{cc}\mathit{\delta }\left({\mathrm{\Omega }}_{1\mathit{n}},{\mathrm{\Omega }}_{21}\right)& \mathit{\delta }\left({\mathrm{\Omega }}_{1\mathit{n}},{\mathrm{\Omega }}_{22}\right)\end{array}& \cdots & \mathit{\delta }\left({\mathrm{\Omega }}_{1\mathit{n}},{\mathrm{\Omega }}_{2\mathit{m}}\right)\end{array}\right]$(64)

Given a complex Θ, dM(Θ, Θ) is also called the internal chromatic-distance matrix of (denoted by iM(Θ)), which can be used to determine the connectivity of a cluster. Replacing all δ = 2 in iM(ξ) by 1 and all others by 0, then we get an adjacency matrix aM(ξ), the same one used in graph theory. The aM(ξ) can be transferred to a reachability matrix rM(ξ) = aM(ξ) + aM(ξ)² + … + aM(ξ)ⁿ, using connectivity algorithms such as Floyd-Warshall, Thorup, or Kameda (Kameda 1975; Cormen et al. 2001; Thorup 2004), if rM(ξ) = 1, then ξ is a connected cluster.

By using Proposition 9 and 10, we can determine Cs–Cs relations by checking whether some particular chromatic distances are found in dM. For example, if we found 0 or 2 in dM, then it means a cell in one cluster is equal or connected to a cell in the other cluster.

Notation 6.

Function cdn(dM, k) returns the number of δ(Ω₁, Ω₂) = k in a chromatic-distance matrix dM(Θ₁, Θ₂). k can be also some conditions such as > 0, or ≠ 2.

Then, we can determine Cs–Cs relations by using dM, cdn function, and the below rules.

(65) $\begin{array}{rl}& {\xi }_1\mathrm{equals}{\xi }_2\iff |{\xi }_2|=\frac{1}{2}\mathrm{cdn}\left(\mathit{dM},0\right)=|{\xi }_2|\\ & {\xi }_1\mathrm{contains}{\xi }_2\iff |{\xi }_2|=\frac{1}{2}\mathrm{cdn}\left(\mathit{dM},0\right)<|{\xi }_2|\\ & {\xi }_1\mathrm{overlaps}{\xi }_2\iff 1\le \frac{1}{2}\mathrm{cdn}\left(\mathit{dM},0\right)<min\left(|{\xi }_1|,|{\xi }_2|\right)\\ & {\xi }_1\mathrm{joints}{\xi }_2\iff \mathrm{cdn}\left(\mathit{dM},\le 0\right)=0\wedge \mathrm{cdn}\left(\mathit{dM},4\right)>0\\ & {\xi }_1\mathrm{touches}{\xi }_2\iff \mathrm{cdn}\left(\mathit{dM},0\right)=0\wedge \mathrm{cdn}\left(\mathit{dM},2\right)>0\\ & {\xi }_1\mathrm{disjoints}{\xi }_2\iff \mathrm{cdn}\left(\mathit{dM},\le 4\right)=0\end{array}$(65)

where dM = dM(ξ₁, ξ₂), and |ξ| is the cardinal number of ξ, that is, if ξis an m-cell cluster, then |ξ| = m.

The third method to determine Cs–Cs relations is directly using their chromatic codes and distance δ(ξ₁, ξ₂), for example, using those codes in Figure 7. Through preliminary work on this method, we found a general rule that the closer the chromatic distance, the closer the spatial topology (Zhu, and Yu 2010). However, the full investigation and more rigorous mathematics of the method remain for future work.

4. Discussions and summary

Full-OACD is a fundamental coding framework involving multidisciplinary theories and applications for the representation and computation of spatial information. In the above sections, we only introduced its basic concepts, generation processing, features, and properties as well as its tentative applications in reasoning spatial topological relations. Our previous and ongoing preliminary work on full-OACDs indicates that the scheme has potential theoretical and applied values related to information coding, combinatorics, group theory, graph theory, complex network, pattern recognition, spatial statistics, and geographical information science.

Through spatial particles and their unique chromatic codes, we are able to directly obtain the spatial relations between them and their generator entities. Spatial relations among entities who live in the space can be also acquired by analyzing their spatial representation and chromatic codes. One of the advantages of full-OACD is that all chromatic codes are integers or half-integers, which are favorites for simple and fast processing in computer information systems.

As one type of spatial chromatic tessellations, full-OACDs provide a scheme to partition and encode space. Compared to the other discrete tessellation models, such as the raster model and Voronoi diagrams (Okabe et al. 2000), the full-OACD is an irregular discrete spatial data model based necessarily on a given entity set. The Voronoi and full-OACD are both generated from an entity set and their basic cells are both with irregular shapes, but the difference is that the cells in full-OACDs are with codes which is a sort of coordinates. Compared to full-OACDs, the raster models do not need generator sets. Moreover, in the raster models, the neighborhood number of a pixel is always 4 or 8, even though the raster’s spatial resolution is very high. In full-OACDs, however, the neighbor number of a cell will become larger and larger as the generator number n goes bigger and bigger. When n turns to be infinite, the space represented by full-OACDs turns to be continuous, and its spatial topology tends to be the classic point-set topology.

Chromatic codes are the keys for characterization, computation, and analysis of spatial particles and their complexes. As a fundamental spatial data model, full-OACD is still in its young stage. Many problems and directions remain unanswered and unexplored. Below we discuss some issues that might be worth further investigation.

4.1. How to use full-OACD in geographical analysis

The geographical interpretation and implication of spatial particles and their chromatic codes. Full-OACD is not only a new type of GIS spatial data model but also a type of spatial tessellation. In a full-OACD, each subspace, namely a spatial particle, is a geographically meaningful region, which implies the specific spatial relations among the generators who made the diagram, and these spatial relations can be interpreted by the chromatic code of the region.

For example, if we try to make a location analysis for five retailers A, B, C, D, and E, and we use the five retailers as the generators to make a full-OACD, in which each geographical region has a chromatic code such as the cell ζ₁ with code (4, 2, 3, 0, 1). The location (index) of each component in ζ₁’s chromatic code indicates the corresponding retailer, and the number of each component indicates the order of the distances from each retailer to the region the larger the number, the nearer the retailer, so we immediately know that this region is the nearest to the retailer A because, at A’s component location (the first number of the chromatic code), its component code is the largest 4. At D’s component location (the fourth number of the chromatic code), its component code is the smallest 0, so we know it is the furthest to the region (cell). Consequently, if in geographical common sense, the distance is often treated as a very important impact factor for retailing, then we can tell that retailer A has the greatest impact on the region, while retailer D has the weakest or no impact.

In full-OACDs, many 2-I and 3-I particles are also spatially significant for geographical analysis, because they can be taken as those competition or equilibrium regions for retailers. We know that any component of a cellular chromatic code is always not equal, since it is always a permutation of base code {0, 1, 2, … , n}, meaning within the region, retailers are in non-equilibrium states without strong competition, because their impacts are always ordered and different, as we showed in the example of retailers A, B, C, D, and E within the cell (4, 2, 3, 0, 1). However, according to properties 5 and 6, some component codes of 2-I or 3-I particles must be the same integers or half-integers, for example, a 3-I particle with chromatic code (1, 1, 3, 1, 4), then we know three retailers A, B, and D have the same impacts on the region, because their components are all 1. We may then conduct a further geographical economic analysis to determine what kind of strategy the three retailers should take for future activities, such as either competing or cooperating. In this case, they may need to cooperate to make them together and stronger to counterweight to retailers C or E, because, let’s take a simple addition if they cooperate, then their impact on this region would be 1 + 1 + 1 = 3, which is almost equal to C’s or E’s impacts 3 or 4.

The above code-based analysis works not only for spatial particles, but also for spatial clusters and complexes, so by exploring the chromatic codes of any sub-region or the whole space of interest, we can rapidly figure out not only the regional or global impacts of a generator (a geographical entity) but also the regional or global relationships among all generators or their any groups.

4.2. How to make full-OACDs more feasible on current computer platforms

The number of spatial particles and their clusters is possibly vast if the size of the generator set is large. Given a generator set with n entities, the number of cells will be the factorial of n (i.e. n!) in an (n–1)-dimensional space, but if those massive particles were projected into a 2d space, then their number will shrink dramatically to O(n⁴). However, n⁴ is still a vast number if n is big. For example, if n = 100, n⁴ will be 100 million, and if n = 1,000, then cell number will approach 1,000 billion. Therefore, we have to consider the problem that how to reduce spatial particle number so that they can be rapidly handled by current computer systems.

We suggest two ways to significantly reduce cell number: (1) using half full-OACDs and (2) using grid-based full-OACDs.

In half full-OACDs, we only consider the subset rather than the entire entity-pair set, and then we will obtain a sub-diagram instead of a complete full-OACD. Such sub-diagrams are equivalent to those half OACDs (h-OACD) introduced in our previous studies (Zhu, and Yu 2010). The smaller the size of the entity-pair subset, the smaller the cell number of the generated full-OACDs. Our tentative study demonstrates that the half full-OACDs are good approximations of the whole full-OACDs in many spatial analyses. For example, full-OACDs and half full-OACDs can be both merged into the same Voronoi diagrams. Such a way is sort of the divide-and-conquer algorithm used in many computations.

In grid-based full-OACD, the cell number will be limited, because, for display, there is always a minimum resolution unit (a pixel) which can be shown on a computer screen or printed on paper. In this way, if two cells are so small and so close that they cannot be discerned by two pixels, then we treat them as one cell. Therefore, given a region of interest, we firstly preset a spatial resolution, for example, 800 × 800, then the final cell number will be no more than 640,000, no matter how many entities (generators) will be used to generate the full-OACD. The original full-OACD is a kind of vector and continuous model, while the grid-based full-OACD is a kind of raster and discrete model. As a result, in grid-based full-OACDs, the lower the resolution of the grid base, the smaller the cell number of the generated full-OACDs.

Given that in half full-OACDs and grid-based full-OACDs, cell number has been already reduced to reasonable sizes, the issues of their updates will be no more problems. In practice, we may generate a half full-OACD in a grid base it combines the advantages of half full-OACD and grid-based full-OACD, so that the computation cost related to cell number and update can be further greatly reduced.

4.3. Spatial representation and topology of geographical entities

In this study, the full-OACD is generated from the generic generators which usually are geometrical points as the reference to generate the SCM space, and therefore the point generators can be artificially set and configured. However, sometimes the real geographical entities are often in shapes and dimensions of lines (e.g. roads and rivers) and areas (e.g. forests and lakes) which can still generate the full-OACDs by using the Equation (1)(1) $\mathit{t}\left(\mathit{p},\left(e_i,e_j\right)\right)=\left\{\begin{array}{c}0,\mathit{d}\left(\mathit{p},e_i\right)>\mathit{d}\left(\mathit{p},e_j\right)\\ 1,\mathit{d}\left(\mathit{p},e_i\right)<\mathit{d}\left(\mathit{p},e_j\right)\\ \frac{1}{2},\mathit{d}\left(\mathit{p},e_i\right)=\mathit{d}\left(\mathit{p},e_j\right)\end{array}\right.$(1) . If the generators are lines or areas, then the distance metric d(p, e) used in Equation (1)(1) $\mathit{t}\left(\mathit{p},\left(e_i,e_j\right)\right)=\left\{\begin{array}{c}0,\mathit{d}\left(\mathit{p},e_i\right)>\mathit{d}\left(\mathit{p},e_j\right)\\ 1,\mathit{d}\left(\mathit{p},e_i\right)<\mathit{d}\left(\mathit{p},e_j\right)\\ \frac{1}{2},\mathit{d}\left(\mathit{p},e_i\right)=\mathit{d}\left(\mathit{p},e_j\right)\end{array}\right.$(1) should be well defined such as the minimal one of the distances from the point p to all points e in the line or area entity.

Spaces in SCM are entity-oriented, meaning that entities are always first, and then they generate the space. Therefore, before the space was generated, the generator entities should have no spatial attributes, and after the space was generated, the spatial attributes of entities will inherit from the space they generated. In other words, entities acquired their spatial coordinates which are expressed by the chromatic codes. A full-OACD contains many points (vertices), segments (edges), and polygons (cells), so it is a kind of continuous vector data model, but on the other hand, these points, segments, and polygons are all elementary spatial particles, so a full-OACD is also a kind of discrete raster data model, and spatial particles play the role of image pixels.

When we try to use full-OACDs in geographical analysis, it raises the question that how to describe the location and spatial features of a geographical entity. Technically, any geographical entity in a full-OACD can be spatially represented by a set of spatial particles, namely, a spatial complex. It is like using a set of pixels to represent a geographical entity in a raster model. The accuracy of a complex-based spatial representation depends on the resolution of a full-OACD. When the generator number n becomes larger and larger, the spatial particle number will correspondingly become even huger and huger in order of n⁴. As a result, every single spatial particle will become smaller and smaller, making the resolution of the generated full-OACD becoming higher and higher. In a high-resolution full-OACD, just like in a high-resolution image, a geographical entity, such as a city or a lake, may occupy massive spatial particles (pixels), and hence form a big spatial complex with a long chromatic code.

Sometimes we are more interested in the topological relationships between geographical entities rather than that between the chromatic spaces, and here the question arises that how to use chromatic codes to represent and reason topology between geographical entities, which typically are in the shapes and dimensions of the point, line, or area. The complete answer to the question remains for future work but here we only provide a tentative resolution. First, we merge chromatic cells to approximate an entity as close as possible, that is, an entity in SCM space may occupy many cells, which is similar to that in the raster model – an entity may occupy many pixels. Next, these entity-occupied and merged cells make a chromatic complex, and hence we can analyze their topological relationships, that is, the spatial topology between complexes using the method proposed in Section 3.1.2.

Note that the full-OACD is essentially a discrete data model and it is different from the well-known Spatial Schema (ISO 19,107) which is based on the vector and continuous data. As a result, in full-OACDs, topological relationships are based on the chromatic codes used as the coordinates of the spatial particles, while in Spatial Schema, topological relationships are usually based on the traditional Euclidean coordinates used for vector data.

4.4. Nonstandard model and singular cells

Full-OACD introduced in this study is a type of standard model, that is, the coding function Equation (1)(1) $\mathit{t}\left(\mathit{p},\left(e_i,e_j\right)\right)=\left\{\begin{array}{c}0,\mathit{d}\left(\mathit{p},e_i\right)>\mathit{d}\left(\mathit{p},e_j\right)\\ 1,\mathit{d}\left(\mathit{p},e_i\right)<\mathit{d}\left(\mathit{p},e_j\right)\\ \frac{1}{2},\mathit{d}\left(\mathit{p},e_i\right)=\mathit{d}\left(\mathit{p},e_j\right)\end{array}\right.$(1) uses the Euclidean distance metric and returns codes 0, 1, and $\frac{1}{2}$, or in an alternative way, spatial partition uses the perpendicular bisectors which divide the space into the exact same halves. However, using Euclidean distance, perpendicular bisectors, and encoding 0, 1, and $\frac{1}{2}$are not necessary for full-OACDs. We can use different coding schemes or partitioning methods in terms of other non-spatial attributes of generator entities, such as ages, colors, or weights, so that the generated spatial tessellations, called nonstandard full-OACDs, will contain distinct spatial particles and chromatic codes from those presented in standard full-OACDs.

In the principle of SCM, the underlying mathematics of generating a full-OACD is neither a coding function nor a half-plane partition. Instead, spaces in SCM are generated and coded by mapping entity–entity relations, just like the R² plane is the mapping of relations (Cartesian products R×R) of the real number field R. Generating of a standard full-OACD is mapping of the ordered relations (symmetric permutation group) of the integer field N. Other entity–entity relations can be also mapped into spaces and hence generate other nonstandard full-OACDs.

There are two types of vertices in full-OACDs: 2-I and 3-I. Their chromatic bases are quite different. The 2-I’s bases have half-integers, but the 3-I’s do not have. In fact, the 3-I vertices are those degenerated cells, or singular cells introduced in previous studies (Zhu, and Yu 2010). In nonstandard full-OACDs, for example, if we use weighted perpendicular bisectors, then 3-I vertices will upgrade their spatial dimensions and hence transform into cells, and meanwhile generating some new edges and 2-I vertices, see the example in Figure 8a. The chromatic bases of these new spatial particles, such as $\left(\frac{1}{2},1,\frac{3}{2}\right)$, are never present in standard full-OACDs.

Figure 8. Other types of spatial chromatic tessellations. (a) Diagrams generated by weighted bisectors; (b) Four generators are concyclic.

In addition, there are no more other types of vertices in a planar full-OACDs,such as 4-I or 5-I, since we have excluded them by assuming the generators are in general cases. For non-generalcases, for example, if four points are concyclic, then their six perpendicular bisectors will intersect at the center of a circle, thus generating a 6-I vertex such that in Figure 8b. Although we can exclude four concyclic points as the non-general2d cases, in 3d space, except that four points are all in a plane (non-general cases), they always build a sphere (general cases), implying that many 6-I vertices will be found in fOACD(n,R³). In Figure 8b, the chromatic base $\left(\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{3}{2}\right)$ of the 6-I vertex is also never present in those general cases of standard full-OACDs.

4.5. Hidden particles and dark space

In terms of the Propositions 6 and 10, as well as the returned results of ∂ζ and ∂η, many spatial particles should theoretically exist in full-OACDs but in real-world spaces, they are hidden. Examining the codes of these hidden particles, we could not find any structural and essential differences from the codes of those emerged particles. The missing of these hidden particles is related to spatial dimensions. In a mathematic world, spatial dimensions could be any high, so any spatial relations should be theoretically allowed and equally existed. However, in the geographical world, spatial dimensions are usually limited in 2d or 3d, so that some relations (spatial particles) cannot be found. Here, we show two analogical examples: (1) if there are three houses in a straight road (1d space), then we can never find a place in the road that is equally distant to the three houses, but if the three houses are in a big farm (2d space), then we can always find that place, namely, the center of the circle passing the three houses; (2) for equation x² +1 = 0, we cannot find its solutions in real number (1d space), but it always has solutions (the complex number i and – i) in 2d planar space.

Given n generators, a standard full-OACD will contain n! cells, but in 2d space, the cell number is only O(n⁴), so we see that most spatial particles are in hidden states, and hence they form a dark space. The lower-dimensional spaces are usually the projections of the higher-dimensional spaces. When a flash of light is projected onto an object, one side of it will be brightened while the other side will be in dark, and if we move or rotate the object, then the bright side may turn to be dark and the dark turns to be bright. It looks like the day and night on the Earth. The same thing happens in full-OACDs: if we change spatial patterns of generators, then some hidden particles will emerge, and meanwhile, some previously emerged particles will be hidden again. Therefore, the hidden particles can be used for spatial pattern analysis of geographical generators, for example, if generators are in irregular and random spatial distributions, then the number of hidden particles would be less, namely, forming a small dark space, and if they are in regular and symmetrical spatial distributions, then the number of hidden particles would be much more, namely, forming a large dark space.

Acknowledgement

The author thanks the understanding and supports of the anonymous reviewers from not only this journal but also the other 20 rejected journals within 8 years. The author also thanks Yiming (Brighter) and Mingxin (Bright Heart) for their caring and giving throughout the author’s whole life since 1973, and particularly during the most difficult days in 2017. What all the above people have done tells that the way of truth and love has always won.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

Data sharing is not applicable to this article as no new data were created or analyzed in this study.

Additional information

Funding

This study is supported by National Natural Science Foundation of China (grant number: 41971373) and Natural Science Foundation of Zhejiang Province (grant number: LY17D10005).

Notes on contributors

Weining Zhu

Weining Zhu received the College and M.S. degrees in Information Physics and Cartography and GIS from Nanjing University, Nanjing, China, in 1995 and 2001, respectively, and the Ph.D. degree in Geosciences from the University of Massachusetts, Amherst, MA, USA, in 2012. Since 2013, he has been an Associate Professor with the Department of Marine Informatics, Ocean College, Zhejiang University. His research interests include GIS, spatial analysis, and remote sensing of environment.