File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: 3D Delaunay triangulation of non-uniform point distributions

Title3D Delaunay triangulation of non-uniform point distributions
Authors
Issue Date2014
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/finel
Citation
Finite Elements in Analysis and Design, 2014, v. 90, p. 113-130 How to Cite?
AbstractIn view of the simplicity and the linearity of regular grid insertion, a multi-grid insertion scheme is proposed for the three-dimensional Delaunay triangulation of non-uniform point distributions by recursive application of the regular grid insertion to an arbitrary subset of the original point set. The fundamentals and difficulties of three-dimensional Delaunay triangulation of highly non-uniformly distributed points by the insertion method are reviewed. Current strategies and methods of point insertions for non-uniformly distributed spatial points are discussed. An enhanced kd-tree insertion algorithm with a specified number of points in a cell and its natural sequence derived from a sandwich insertion scheme is also presented. The regular grid insertion, the enhanced kd-tree insertion and the multi-grid insertion have been rigorously studied with benchmark non-uniform distributions of 0.4–20 million points. It is found that the kd-tree insertion is more efficient in locating the base tetrahedron, but it is also more sensitive to the triangulation of non-uniform point distributions with a large amount of conflicting elongated tetrahedra. Including the grid construction time, multi-grid insertion is the most stable and efficient for all the uniform and non-uniform point distributions tested.
Persistent Identifierhttp://hdl.handle.net/10722/210702
ISSN
2015 Impact Factor: 2.175
2015 SCImago Journal Rankings: 1.278

 

DC FieldValueLanguage
dc.contributor.authorLo, SH-
dc.date.accessioned2015-06-23T05:47:48Z-
dc.date.available2015-06-23T05:47:48Z-
dc.date.issued2014-
dc.identifier.citationFinite Elements in Analysis and Design, 2014, v. 90, p. 113-130-
dc.identifier.issn0168-874X-
dc.identifier.urihttp://hdl.handle.net/10722/210702-
dc.description.abstractIn view of the simplicity and the linearity of regular grid insertion, a multi-grid insertion scheme is proposed for the three-dimensional Delaunay triangulation of non-uniform point distributions by recursive application of the regular grid insertion to an arbitrary subset of the original point set. The fundamentals and difficulties of three-dimensional Delaunay triangulation of highly non-uniformly distributed points by the insertion method are reviewed. Current strategies and methods of point insertions for non-uniformly distributed spatial points are discussed. An enhanced kd-tree insertion algorithm with a specified number of points in a cell and its natural sequence derived from a sandwich insertion scheme is also presented. The regular grid insertion, the enhanced kd-tree insertion and the multi-grid insertion have been rigorously studied with benchmark non-uniform distributions of 0.4–20 million points. It is found that the kd-tree insertion is more efficient in locating the base tetrahedron, but it is also more sensitive to the triangulation of non-uniform point distributions with a large amount of conflicting elongated tetrahedra. Including the grid construction time, multi-grid insertion is the most stable and efficient for all the uniform and non-uniform point distributions tested.-
dc.languageeng-
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/finel-
dc.relation.ispartofFinite Elements in Analysis and Design-
dc.rightsPosting accepted manuscript (postprint): © 2014. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.title3D Delaunay triangulation of non-uniform point distributions-
dc.typeArticle-
dc.identifier.emailLo, SH: hreclsh@hkucc.hku.hk-
dc.identifier.authorityLo, SH=rp00223-
dc.description.naturepostprint-
dc.identifier.doi10.1016/j.finel.2014.07.002-
dc.identifier.hkuros243640-
dc.identifier.volume90-
dc.identifier.spage113-
dc.identifier.epage130-
dc.publisher.placeNetherlands-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats