联机Fermat场址问题及一些相关问题的求解算法

摘要：

Fermat 场址问题要求在平面上寻找一点,使该点到一个给定点集中所有各点的距离之和取得最小值.联机Fermat场址问题进一步要求可以在给出点集中任意地做点的插入或删除.利用在科学计算可视化研究中讨论的等值线抽取技术来分析此问题,获得了一个联机求解的算法.应用获得算法的框架,还可以求解在平面内寻找某个特定点位置的一类问题及其它一些相关问题,对此给出了3个实例:联机的最大空圆问题、最小包围圆问题以及联机范围查找问题.实践表明给出的解法有广泛的应用.

关键词：联机算法、等值线、Fermat场址、最大空圆、最小包围圆、范围查找、计算几何

所属期刊栏目：11

分类号：TP391(计算技术、计算机技术)

资助基金：中国科学院资助项目69673031

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：481-484