Finding a Region with the Minimum Total L1 Distance from Prescribed Terminals
Finding a Region with the Minimum Total L1 Distance from Prescribed Terminals
复制标题
查找距指定终端总 L1 距离最小的区域
DOI：
10.1007/s00453-002-0997-y
复制
发表时间：
2003
期刊：
影响因子：
1.1
通讯作者：
Yoshiyuki Takao
中科院分区：
文献类型：
--
作者：
Yoshiyuki Takao
给定平面上的k个端点和n个轴平行的矩形障碍物，我们的算法找到一个平面区域R*，使得对于R*中的任意点p，连接p和k个端点且不经过任何障碍物的最短直线路径的总长度最小。该算法对输出敏感，如果K是一个固定常数，则需要O（(K+n) log n）时间和O（K+n）空间，其中K是找到的区域R*的多边形顶点的总数。
Given k terminals and n axis-parallel rectangular obstacles on the plane, our algorithm finds a plane region R* such that, for any point p in R*, the total length of the k shortest rectilinear paths connecting p and the k terminals without passing through any obstacle is minimum. The algorithm is output-sensitive, and takes O((K+n) log n) time and O(K+n) space if k is a fixed constant, where K is the total number of polygonal vertices of the found region R*.