数值计算与计算机应用 2001, 22(4 ) 267-275 DOI:     ISSN: 1000-3266 CN: 11-2124/TP

本期目录 | 下期目录 | 过刊浏览 | 高级检索                                                            [打印本页]   [关闭]
论文
扩展功能
本文信息
Supporting info
PDF(474KB)
[HTML全文](0KB)
参考文献[PDF]
参考文献
服务与反馈
把本文推荐给朋友
加入我的书架
加入引用管理器
引用本文
Email Alert
文章反馈
浏览反馈信息
本文关键词相关文章
本文作者相关文章
PubMed

Delaunay三角网格的一种快速生成法

邬吉明,沈隆钧,张景琳

北京应用物理与计算数学研究所;计算物理实验室 ;北京应用物理与计算数学研究所;计算物理实验室 ;北京应用物理与计算数学研究所;计算物理实验室

摘要

关键词

A FAST ALGORITHM FOR GENERATING DELAUNAY TRIANGULATION

Wu Jiming,Shen Longjun,Zhang Jinglin (Laboratory of Computational Physics, Institute of Applied Physics and Computational Mathematics, Beijing 100088)

Abstract:

Delaunay triangulation has been widely used in many fields such as compu- tational fluid dynamics, statistics, meteorology solid state physics, computational geometry and so on. Bowyer-Watson algorithm is a very popular one for generating Delaunay triangulation. In generating the Delaunay triangulation of a preassigned set of n points, the complexity of Bowyer-Watson algorithm can at most be reduced to O(n log n) for the simple reason that the complexity of its tree search process is O(nlog n). In this paper we suggest a tree search technique whose complexity is O(n). Noting that the order of point insertion can affect the efficiency of Bowyer- Watson algorithm, we propose a technique to optimize the point insertion process. Based on these two techniques, we obtain a fast algorithm for generating Delaunay triangulation.

Keywords:
收稿日期  修回日期  网络版发布日期  
DOI:
基金项目:

通讯作者:
作者简介:

本刊中的类似文章

Copyright 2008 by 数值计算与计算机应用