Karimipour Farid Abstract: Extension of 2D spatial analyses  i.e., a set of operations applied on a
spatial data set  to higher dimensions, e.g., 3D and temporal, is one
of the requirements to handle real world phenomena in GIS. The current
approach is to design a technical solution to extend a certain 2D
spatial analysis to a new multidimensional space with the least
increase in complexity and speed. This technical approach has resulted
in developments that cannot be generalized. The result of following such
an approach in the software development stage is recoding each spatial
analysis, separately, for each dimension. Therefore, the code for a,
say, general 2D/3D static and moving objects supporting GIS is nearly
four times the current code size, offering four variants: static 2D,
moving 2D, static 3D, and moving 3D. The complexity of such a growth of
code written in one of the currently popular programming languages, say,
C++ is hard to manage, resulting in numerous bugs.
This thesis investigates spatial analyses based on their dimension
independent characteristics (i.e., independent of the objects to which
the analyses are applied), toward achieving a general solution. It
intends to provide an integrated framework for spatial analyses of
different multidimensional spaces a GIS should support. This framework
will be independent of the objects to which the analyses are applied and
spatial analyses are formally defined by combinations of the elements
of this integrated framework.
To implement this approach, spatial analyses are formally expressed
hierarchically where each analysis is defined as a combination of
simpler ones. These definitions are independent of dimension and the
hierarchy ends in a set of primary operations, which are not further
decomposed. A set of required data types are also identified. Having
implemented the dimensionally independent data types and operations,
they all will be extended to a specific space (e.g., moving points) by
applying the mappings between defined the spaces.
The required abstraction of the proposed approach is the subject of
algebra that ignores those properties of operations that depend on the
objects they are applied to. The desired spaces are structurally
equivalent, so they are described by the same algebra. Having
implemented the required data types and operations, their extension to a
specific space is viable by applying the (structure preserving)
mapping.
The proposed approach has been evaluated through implementation of
Delaunay triangulation for 2D and 3D static and moving points in the
functional programming language Haskell and their efficiency has been
evaluated. The implementations were used in two applications, i.e.,
convex decomposition of polytops and optimum placement of a sensor
network based on the moving Voronoi diagram, in order to show how the
proposed approach can be practically used. The achieved results certify
the hypothesis of the research says that "studying spatial analyses
based on their dimension independent characteristics leads to a
consistent solution toward implementation of a multidimensional GIS".
Complexity and speed are factors used to evaluate the performance of an
extension technique in current research. However, the aim here is to
avoid recoding each spatial analysis for each dimension. Thus, the main
concern of this research is on the mathematical validation of the
conceptual framework and investigation of its implementation issues.
Nevertheless, the results show that the proposed approach does not
affect the big O complexity and speed for applying the spatial analyses
on objects of higher dimensions.
A Formal Approach to Implement Dimension Independent Spatial Analyses [16.6.2011] (Farid Karimipour)

