[Zurück]

F. Karimipour:
"A Formal Approach to Implement Dimension Independent Spatial Analyses";
Betreuer/in(nen), Begutachter/in(nen): A. Frank, W. Kropatsch; Department of Geoinformation, 2011; Rigorosum: 16.06.2011.

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 multi-dimensional 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 multi-dimensional 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 multi-dimensional 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.

Multi-dimensional spatial analyses, 3D spatial data, Moving objects, Formal theories, Abstraction, Algebraic structures, Algebraic specifications, Lifting, Delaunay triangulation, Voronoi diagram, Functional programming languages, Haskell

http://publik.tuwien.ac.at/files/PubDat_196996.pdf