Connectivity Graphs of Uncertainty Regions
Connectivity Graphs of Uncertainty Regions
复制标题
不确定区域的连通图
DOI：
10.1007/s00453-016-0191-2
复制
发表时间：
2016
期刊：
影响因子：
1.1
通讯作者：
Chambers E
中科院分区：
文献类型：
--
作者：
Chambers E
我们研究点之间的连接关系，其中每个输入点的精确位置位于不确定区域。我们区分了出现不确定性的两种基本情况。在有利的最佳情况不确定性中，可以从给定的集合中选择每个输入点，以产生最佳的目标值。在不利的最坏情况不确定性中，输入集在所有可能的点位置中具有最差的可能目标值，这些点位置由于例如不精确的数据而不确定。我们考虑瓶颈生成树问题的这些不确定性概念，从而产生以下与不确定性问题的最佳情况连通性：给定一系列几何区域，每个区域选择一个点，使得相关几何生成树的最长边长度最小化。我们证明，即使对于区域是线段或正方形的非常简单的场景，这个问题也是 NP 困难的。另一方面，我们给出了存在区域的情况的精确解，其中k个区域是线段并且n个区域是不动点。然后，我们针对区域全部是线段或全部单位圆盘的情况给出近似算法。我们还为相应的不确定性问题的最坏情况连通性问题提供了近似方法：给定一组不确定性区域，找到最小距离r，使得对于任何点选择（每个区域一个），在边长度最多的点之间存在一棵生成树。
We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorableBest-Case Uncertainty, each input point can be chosen from a given set to yield the best possible objective value. In the unfavorableWorst-Case Uncertainty, the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the followingBest-Case Connectivity with Uncertaintyproblem: given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there areregions, wherekof the regions are line segments andnof the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the correspondingWorst-Case Connectivity with Uncertaintyproblem: Given a set of uncertainty regions, find the minimal distancersuch that for any choice of points, one per region, there is a spanning tree among the points with edge length at mostr.
登录
查看更多内容
不精确点的最大最短路径
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
Y. Disser;Matús Mihalák;S. Montanari
通讯作者：
S. Montanari
DOI：
10.1016/j.comgeo.2012.10.009
发表时间：
2014
期刊：
Comput. Geom.
影响因子：
--
作者：
Esther M. Arkin;Claudia Dieckmann;Christian Knauer;Joseph S.B. Mitchell;Valentin Polishchuk;Lena Schlipf;Shang Yang
通讯作者：
Shang Yang
影响因子：
0.5
作者：
Reza Dorrigiv;Robert Fraser;Meng He;Shahin Kamali;A. Kawamura;A. López-Ortiz;Diego Seco
通讯作者：
Reza Dorrigiv;Robert Fraser;Meng He;Shahin Kamali;A. Kawamura;A. López-Ortiz;Diego Seco
几何游览和网络设计问题的近似算法（扩展摘要）
DOI：
--
发表时间：
1995
期刊：
SCG '95
影响因子：
--
作者：
Cristian S. Mata;Joseph S. B. Mitchell
通讯作者：
Joseph S. B. Mitchell
DOI：
10.1016/0012-365x(83)90128-0
发表时间：
1983
期刊：
Discret. Math.
影响因子：
--
作者：
P. Duchet;Y. O. Hamidoune;M. Vergnas;H. Meyniel
通讯作者：
H. Meyniel