Article: A new algorithm for fast updating Delaunay triangulation of moving points based on local fixing

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleA new algorithm for fast updating Delaunay triangulation of moving points based on local fixing
AuthorsZhou, Y2 3
Sun, F3
Wang, W3
Wang, J1 4
Zhang, C1 2 4
KeywordsBi-Cell
Delaunay Triangulation
Filtering
Reverse Fixing
Issue Date2011
CitationJisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal Of Computer-Aided Design And Computer Graphics, 2011, v. 23 n. 12, p. 2006-2012 [How to Cite?]
AbstractFor updating a Delaunay triangulation of moving points, bi-cell filtering method can find the most bi-cells whose Delaunay connectivities remain unchanged after the points are slightly perturbed. When flipped bi-cells occur, rebuilding method for all points has to be applied. In this paper, we present a new algorithm that improves the performance of the original bi-cell filtering algorithm via checking and fixing flipped bi-cells locally. Experimental results show that the new algorithm runs 20% to 30% faster than the original algorithm when rebuilding method is applied frequently.
ISSN1003-9775
2011 SCImago Journal Rankings: 0.032
ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorZhou, Y
dc.contributor.authorSun, F
dc.contributor.authorWang, W
dc.contributor.authorWang, J
dc.contributor.authorZhang, C
dc.date.accessioned2012-06-26T06:39:33Z
dc.date.available2012-06-26T06:39:33Z
dc.date.issued2011
dc.description.abstractFor updating a Delaunay triangulation of moving points, bi-cell filtering method can find the most bi-cells whose Delaunay connectivities remain unchanged after the points are slightly perturbed. When flipped bi-cells occur, rebuilding method for all points has to be applied. In this paper, we present a new algorithm that improves the performance of the original bi-cell filtering algorithm via checking and fixing flipped bi-cells locally. Experimental results show that the new algorithm runs 20% to 30% faster than the original algorithm when rebuilding method is applied frequently.
dc.description.natureLink_to_subscribed_fulltext
dc.identifier.citationJisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal Of Computer-Aided Design And Computer Graphics, 2011, v. 23 n. 12, p. 2006-2012 [How to Cite?]
dc.identifier.epage2012
dc.identifier.issn1003-9775
2011 SCImago Journal Rankings: 0.032
dc.identifier.issue12
dc.identifier.scopuseid_2-s2.0-83055195384
dc.identifier.spage2006
dc.identifier.urihttp://hdl.handle.net/10722/152483
dc.identifier.volume23
dc.languageeng
dc.relation.ispartofJisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics
dc.relation.referencesReferences in Scopus
dc.subjectBi-Cell
dc.subjectDelaunay Triangulation
dc.subjectFiltering
dc.subjectReverse Fixing
dc.titleA new algorithm for fast updating Delaunay triangulation of moving points based on local fixing
dc.typeArticle
Author Affiliations
  1. Shandong University of Finance
  2. Shandong University
  3. The University of Hong Kong
  4. null