Development of an Exact Algorithm for Computing Minimum Weight Triangulations
Development of an Exact Algorithm for Computing Minimum Weight Triangulations
批准号:
08680377
负责人:
KATOH Naoki
金额:
$1.47万
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research (C)
财政年份:
1996
资助国家:
日本
项目状态:
已结题
起止时间:
1996 至 1997
中文摘要
在过去的两年里,我们一直试图开发一种有效的精确算法来计算平面上点的最小权三角剖分(简称MWT)。为此,我们首先发展了一种新的方法来计算MWT长度的有效下界,该方法基于任意两个三角剖分的适当定义的图的最小umu权匹配。通过计算实验验证了提出的下界非常接近最优值,并提出了一种0(n^3logn)算法来计算MWT子图的LMT-骨架,并对随机生成的点集进行了计算实验,以了解LMT-骨架有多大。结果表明,在大多数情况下,LMT-骨架是连通的,这意味着可以在实际意义上有效地计算MWT。结合这两个思想,我们提出了一种计算MWT的分枝定界算法,并将我们的算法应用于LMT-骨架高度不连通的几个硬实例。计算结果表明,该算法能较好地计算复杂情况下的MWT,并考虑了具有角度约束且最大和/或最小角度小于(或大于)或等于给定阈值的MWT问题。最后,我们将建筑中遇到的结构优化问题描述为MWT问题的一种变体。特别地,我们考虑了在考虑结构特性的约束下,三角桁架的拓扑结构和节点位置的寻找和优化问题。
英文摘要
Over the last two yeras, we have tried to develop an efficient exact algorithm for computing a minimum weight triangulation (MWT for short) for points in the plane. For this purpose we have first developed a new way to compute an effective lower bound on the length of MWT,based on the miniumu weight matching of a graph appropriately defined for arbitrary two triangulations. We have verified by computational experimetns that the proposed lower bound is very close to the optimal.We also developed an 0 (n^3logn) algorithm for computing an LMT-skeleton which is subgraph of MWT.We have carried out computational experiments for randomly generated point sets in order to see how large LMT-skeletons are. The results demonstrated that for most cases LMT-skeleton becomes connected, implying that MWT can be computed efficiently in a practical sense.Combining these tow ideas, we then developed a branch and bound algorithm for computing MWT.We have applied our algorithm to several hard instances whose LMT-skeletons are highly disconnected. Computational results showed that the proposed algorithm can compute MWT for such hard instances.We also considered a problem of computing MWT with angular constrants such that maximum and/or minimum angles are less than (resp.larger than) or equal to a given threshold. We have developed an algorithm for computing LMT-skeletons for such constrained MWT.Finally, we formulated structural optimization problems we encounter in architecture as a variant of MWT problems. In particular, we considered a problem of finding and optimal topology and node positions of triangular trusses under the constraint concerning strudtural characteristics.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
M.Ohsaki and H.Tagawa: "Genetic algorithm for simultaneous optimization of topology and geometry of a regular plane truss" Proc.Int.Symposium on Optimization and Innovative Design(OPID97),Japan Soc.of Mech.Engineers. #121 (1997)
M.Ohsaki 和 H.Takawa:“规则平面桁架拓扑和几何结构同步优化的遗传算法”Proc.Int.Symposium on Optimization and Innovative Design(OPID97),Japan Soc.of Mech.Engineers。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
M.Ohsaki: "Simultanecus optimization of topology and geometry of aregular plane truss" Comput.& Struct.66(1). 69-77 (1997)
M.Ohsaki:“正平面桁架拓扑和几何的同步优化”计算。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
S. Cheng: "The Study of the LMT-Skeleton" Proc. of ISAAC '96. 834. 256-265 (1996)
S. Cheng:“LMT-骨骼的研究”Proc。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
O.Aichholzer, F.Aurenhammer, Siu-Wing Cheng, N.Katoh, G.Rote, M.Taschwer and Ying-Feng Xu: "Triangulations Intersect Nicely" Discrete Computational Geometry. Vol.16. 339-359 (1996)
O.Aichholzer、F.Aurenhammer、Siu-Wing Cheng、N.Katoh、G.Rote、M.Taschwer 和 Ying-Feng Xu:“三角剖分很好地相交”离散计算几何。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
M.Ohsaki: "Simultaneous optimization of topology and geometry of a regular plane truss" Comput. & Struct. Vol.66(1). 69-77 (1997)
M.Ohsaki:“规则平面桁架的拓扑和几何的同时优化”计算。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
共 9 条
Computational Geometry and Discrete Optimization in Architecture and Urban Planning
-
批准号:21300003
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$7.32万
-
财政年份:2009
-
负责人:KATOH Naoki
-
依托单位:
Extraction of Geometric Structures in Architecture and City Planning and Development of their Enumeration Algorithms
-
批准号:19500013
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.91万
-
财政年份:2007
-
负责人:KATOH Naoki
-
依托单位:
Practical Algorithms for Knowledge Discovery from High-Dimensional Data based on Computational Geometry
-
批准号:17500007
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$1.79万
-
财政年份:2005
-
负责人:KATOH Naoki
-
依托单位:
Development of Algorithms for Geometric Optimization and Data Analysis in Architecute
-
批准号:13680412
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.18万
-
财政年份:2001
-
负责人:KATOH Naoki
-
依托单位:
Development of geometric algorithms in architectural planning and architectural structures
-
批准号:10205214
-
项目类别:Grant-in-Aid for Scientific Research on Priority Areas (B)
-
资助金额:$6.72万
-
财政年份:1998
-
负责人:KATOH Naoki
-
依托单位:
Development of Optimal Algorithms for Partitioning Geometric Data
-
批准号:10680353
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$1.02万
-
财政年份:1998
-
负责人:KATOH Naoki
-
依托单位:
On Construction and Evaluation of Parallel and Randomized Algorithms for Network Optimization Problems
-
批准号:05680281
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$1.22万
-
财政年份:1993
-
负责人:KATOH Naoki
-
依托单位:
海外基金