【平面划分下点的查找王保华】.pdf
平面划分下的点的定位.
0引吾以及问题的提出.点集,E是S中的边集.G(S)是一个平面直线图。特别说明一下,边已中的边有可能含有半直线,即是一条具有一个有穷主端点。一个 无穷立常点的边.问题的提出:给定一个平面直线划分S,如何建立一个有效 的数据结构,使得任给平面中一点,能迅速地定位出在S 的哪一个区域内.平面直线划分下的点的定位问题是计算几何的基本 研究课题之一,关于这方面的问题出版了大量文章,人们提出 了各中不同类型的角羊决才法,其中达到最优结构的有:的一个结构,该结构存储花费为0(1v1),点定位时间为ollg1m) 其中M表未丁负点集V的基数.这是一个最忧的结构,但这只是从 数太大,故缺乏实用性。
用0(的ngh)的时间可以给出任一查询点的邻近点的信息.上述定理中构造的数据结构就是运河一树,具体是怎么 构造和怎么查找邻近点信息,的,这一节中我们暂且不说,只要知道有 这个结果就行了.后面的第四部分都可以认为是这一结果的实 际应用,在那里我们再介绍相应操作.2给平面直线划分的边续木号.定义21:设有间图G=(v,E),V是G的顶点集,它的基数IM=N, 正是G的边的合,我们说G是可拓朴排序的,如果存在一个一 一对应的映射f.V>{1,,N},使得若vv＜E,则有:f(v)