| 矩形集上的点定位 |
| |
| 引用本文： | 林仙丽,傅清祥. 矩形集上的点定位[J]. 福州大学学报(自然科学版), 1999, 27(4): 1-28 |
| |
| 作者姓名： | 林仙丽 傅清祥 |
| |
| 作者单位： | 福州大学计算机科学与技术系,福建福州,350002 |
| |
| 基金项目： | 福建省火炬计划资助项目 |
| |
| 摘 要： | 给出解决计算几何问题的两种算法， 其预处理部分分别基于对 Ｓ 的平面扫描和 Ｓ 在ｘ 轴的投影线段对应的线段树除描述算法的步骤外， 还进行算法的复杂性分析这两个算法可直接推广到等置矩形和ｄ 维空间的情形
|
| 关 键 词： | 计算几何 算法 点定位 平面扫描 线段树 |
| 修稿时间： | 1998-08-03 |
Location of a Point in a Set of Rectangles |
| |
| LIN Xian-li,FU Qing-xiang. Location of a Point in a Set of Rectangles[J]. Journal of Fuzhou University(Natural Science Edition), 1999, 27(4): 1-28 |
| |
| Authors: | LIN Xian-li FU Qing-xiang |
| |
| Affiliation: | L I N Xian - li, F U Qing - xiang( Department of Computer Science and Technology , Fuzhou University , Fujian Fuzhou 350002 , China) |
| |
| Abstract: | This paper presents two algorithms for the geomentric problem , one is based on the planescanning to S,and the other on the corresponding line segmenttree of the projection segments of rect angles of Sin xaxis It not only describes the steps of the algorithms , but analyses their complexity Both algorithms can be extended to isothetic rectangle and d - dimensional space |
| |
| Keywords: | computational geometry algorithm point - location plane sweep segment tree |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《福州大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《福州大学学报(自然科学版)》下载免费的PDF全文 |
