几何区域查询问题是计算几何领域的一个重要研究内容,它来源于数据库和地理信息系统应用的需求而产生并迅速发展,同时在计算机图形学、模式识别等领域得到了广泛的应用。该问题往往是某一领域中的关键性子问题,如光线追踪、隐藏面消除、相交性判定、相似性查询、最近邻查询等。数据查询的实质是对数据的分类索引的过程,一般分为两类:一类是对数据空间的分割,将整个数据空间递归划分为一系列子空间;另一类是将高维空间中的数据对象映射到一维空间中,然后利用一维空间中数据间的有序性高效的处理数据。本文主要做了以下工作:1.回顾了计算几何及几何区域查询的相关理论、常见的区域查询类型以及国内外的研究现状。从数学理论的角度出发,利用代数学中半群的概念,在加权意义下给出了区域查询问题统一的理论模型,并利用耗费函数作为衡量算法效率的计算模型,为区域查询算法的提出、实现及复杂度分析提供了理论依据和判断准则。2.对正交区域查询问题的一些经典数据组织结构的构建思想、查询算法及实现方法做了详细分析和研究,这是进行算法改进和创新的基础和依据。3.根据数据对象多个属性间重要性的差异,采用“粗筛”与“细筛”相结合,层次化的查询结构对数据空间进行了分割。首先,对数据对象进行大尺度的粗选,排除大量无关数据;其次,采用较小的尺度进一步缩小可选集的范围;最后,采用精确的查询。具体来讲,为了获得较高的查询和动态更新效率并且提高数据组织的灵活性,采用了以地址方式存储数据的链表结构作为基本数据载体;为了实现不同尺度的分割,采用了改进的1-3确定性跳跃表;由于链表是一种线性存储结构较难用于高维数据对象,为此采用了将一维链表映射到高维空间的办法实现了层次化数据结构,使其成为适应高维空间区域查询的索引结构。该结构继承了跳跃表的优点。利用确定性跳跃表来代替高度递归的区域查询树,该结构既实现了对k维空间区域查询的高效性,又规避了跳跃表结构本身的缺点。本文给出了该结构的完整定义,并给出了该结构的实现算法以及建立在该结构之上的查询、插入和删除算法。通过对计算模型分析证明了相应算法复杂度。