非精确数据主要有两类因素造成。第一类是客观因素。例如,计算机存储量有限导致大部分存储的实数是经过四舍五入处理的近似值。第二类因素是主观因素。例如,为了保护个人隐私会采取泛化数据等方式故意构造非精确数据。计算几何是计算机算法领域的一个重要分支,该领域研究的基本算法有着广泛的应用。但是计算几何算法主要是基于精确数据点的。如果在面对非精确数据的时候仍然简单套用传统算法,轻则可能造成计算不准确、资源浪费,重则可能造成严重的计算错误。本文主要研究非精确数据模型下计算几何问题。　　 主要贡献如下:　　 1.在基于连续区域模型的凸包最优值问题方面的贡献:本文对连续区域模型下的凸包最优值问题进行了研究,给出了其中一些问题的高效算法。这些问题有:本文给出了时间复杂度为O(nlogn)的算法解决基于等长平行线段模型的最大面积凸包问题,时间复杂度为O(n3+nm)的算法解决混有平行线段和点的最大面积凸包问题(n为平行线段的数目,m为点的数目),时间复杂度为O(n4)的算法解决基于平行线段模型的最大周长凸包算法,时间复杂度为O(n5)的算法解决基于不可重叠正方形为模型的非精确数据的最大面积凸包,时间复杂度为O(n2)的算法解决基于可重叠等大小正方形为模型的非精确数据的最大面积凸包问题,时间复杂度为O(n2)的算法解决基于固定点都在凸包上和时间复杂度为O(nlogn)的近似算法解决(近似解和最优解之间最多相差一个正方形面积)基于不可重叠等大小正方形为模型的非精确数据的最大面积凸包问题。　　 2.在颜色支撑点集模型(离散模型)下最优值问题方面的贡献:本文对于颜色支撑点集模型下的几何体的最优值问题进行了研究,证明了颜色支撑点集模型下的最近点对最大值问题、最小、最大可能最小生成树问题、最小周长凸包问题是NP完全问题。同时本文对于最小周长凸包问题给出了一个√2的近似算法、证明了为最近点对最大值问题寻找近似因子小于2的常数因子近似算法是NP难的并且给出了一个时间复杂度为O(nlogn)的算法求解颜色支撑点集模型下的最大直径问题。　　 3.在颜色支撑点集模型(离散模型)下的一些几何度量的期望值问题方面的贡献:期望值是概率统计中的一个重要参数,它有着非常广泛的应用。比如,在计算机算法分析理论中,期望时间复杂度是衡量算法优劣的重要标志之一。本文首次提出颜色支撑点集模型下的一些几何问题的期望值问题,并对其进行了研究。本文给出了时间复杂度为O(n2logn)的两个算法分别求解基于颜色支撑点集的凸包的周长期望值和面积期望值问题,时间复杂度为O(nlogn)的算法求解基于颜色支撑点集的轴对齐矩形的周长期望值和时间复杂度为O(n2)的算法求解基于颜色支撑点集的轴对齐矩形的面积期望值,并且还证明了如果P≠NP则基于颜色支撑点集的最小点对距离期望值是没有多项式时间的算法。本文的研究填补了基于非精确数据计算几何算法的空白,并对部分已有算法进行了优化降低了算法的时间复杂度,为这些问题的应用打下了理论基础。