摘要
Ｆｅｒｍ ａｔ 场址问题要求在平面上寻找一点，使该点到一个给定点集中所有各点的距离之和取得最小值．联机Ｆｅｒｍ ａｔ场址问题进一步要求可以在给出点集中任意地做点的插入或删除．利用在科学计算可视化研究中讨论的等值线抽取技术来分析此问题，获得了一个联机求解的算法．应用获得算法的框架，还可以求解在平面内寻找某个特定点位置的一类问题及其它一些相关问题，对此给出了３个实例：联机的最大空圆问题、最小包围圆问题以及联机范围查找问题．实践表明给出的解法有广泛的应用．
The Fermat location problem consists of searching for a point on a plane, such that the sum of distances from the feature point to each point in the given set is minimized. On line Fermat location problem arises when points are allowed to be inserted or deleted arbitrarily in the given point set. The problem is tackled using contour line extracting technique in scientific visualization, and an on line performance is obtained. The presented method can be considered as a generic one for solving a series of problems where some specific location is searched in a plane and other related issues. Three examples: on line largest empty circle, on line smallest enclosing circle, and on line range search, are shown here. Case studies show that the given method has wide field of applications.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
1999年第6期481-484,共4页
Journal of Computer-Aided Design & Computer Graphics
基金
国家自然科学基金
关键词
联机算法
等值线
Fermat场址
计算几何
on line algorithm, contour line, Fermat location, largest empty circle, smallest enclosing circle, range search, computational geometry
