Algorithm Research On Geometric Range Query

The geometric range query problem is an important research content in computational geometry. It arises in the need for the applications of database and geographic information system (GIS), develops rapaidly and finds its wide applications in computer graphics, pattern recognition etc.. It is usually a crucial subroutine in a certain field such as ray tracing, hidden-surface removal, intersection judge, similarity query and nearest neighbor query.Essentially, data query is the process of classifying data objects. Generally, it can be solved in two different ways: one is to partition the data space, in which the whole data space is recursively partitioned into a series of subspaces; the other is to map data objects in high dimensional space into one-dimensional space first, then to be dealt by using the order between data in one-dimensional space with high efficiency.The main research work of this paper is as follows:1. The related theory in computational geometry and geometric range query, common types of range queries and the domestic and international research development are introduced. From the view of mathematics, the united theoretical model for range query by using the concept of semi-group in algebra under the meaning of weight is given. And cost functions are used as computational model to portray and analyze an algorithm's efficiency, which provides theoretical judge rule for the proposal and implementation of range query algorithms and their complexity analysis.2. The construction ideas of classic data organization structures in orthogonal range query, query algorithms and their implementation are analysed and studied in detail and deeply, which is the basis for us to make improvement and creation for related algorithms.3. Data space is partitioned according to the difference of the importance between attributes of data objects by hierarchical query structure, combining coarse screening and refine screening. At the beginning, rugged grid is used to exclude a large amount of unrelated data objects. Then, a refined grid is used to reduce the scope for selectable objects further by taking smaller scales. Finally an accurate query is taken. In detail, linked list structures, in which data is stored in address, are adopted as basic data carrier to achieve the high efficiency of query and dynamic updating and to improve the flexibility of data organization; The improved 1-3 deterministic skip list is taken to carry out the partition for data space under different scales. Hierarchical data structure is realized by mapping linked lists in one-dimensional space into high dimensional space to make it be the index structure suitable to range query in high dimensional space due to the fact that a linked list is linear storage structure difficult to be applied in high dimensional space. The structure inherits the advantages of the skip list. The query of high efficiency in k-dimensional space is realized by replacing height-recursive range query by the deterministic skip list, meanwhile the drawback (random undeterministic factors) can de avoided. The complete definition of this kind of structure, its implementation algorithm and range query, node insertion and deletion algorithms based on this structure are given. The time complexities of the corresponding algorithms are achieved by analyzing the computational model.