File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.finel.2014.07.002
- Scopus: eid_2-s2.0-84904891369
- WOS: WOS:000340990600012
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: 3D Delaunay triangulation of non-uniform point distributions
Title | 3D Delaunay triangulation of non-uniform point distributions |
---|---|
Authors | |
Keywords | 3D Delaunay triangulation kd-Tree insertions Multi-grid Non-uniform point distributions Regular grid |
Issue Date | 2014 |
Publisher | Elsevier 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? |
Abstract | In 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 Identifier | http://hdl.handle.net/10722/210702 |
ISSN | 2023 Impact Factor: 3.5 2023 SCImago Journal Rankings: 0.835 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lo, SH | - |
dc.date.accessioned | 2015-06-23T05:47:48Z | - |
dc.date.available | 2015-06-23T05:47:48Z | - |
dc.date.issued | 2014 | - |
dc.identifier.citation | Finite Elements in Analysis and Design, 2014, v. 90, p. 113-130 | - |
dc.identifier.issn | 0168-874X | - |
dc.identifier.uri | http://hdl.handle.net/10722/210702 | - |
dc.description.abstract | In 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.language | eng | - |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/finel | - |
dc.relation.ispartof | Finite Elements in Analysis and Design | - |
dc.rights | This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | - |
dc.subject | 3D Delaunay triangulation | - |
dc.subject | kd-Tree insertions | - |
dc.subject | Multi-grid | - |
dc.subject | Non-uniform point distributions | - |
dc.subject | Regular grid | - |
dc.title | 3D Delaunay triangulation of non-uniform point distributions | - |
dc.type | Article | - |
dc.identifier.email | Lo, SH: hreclsh@hkucc.hku.hk | - |
dc.identifier.authority | Lo, SH=rp00223 | - |
dc.description.nature | postprint | - |
dc.identifier.doi | 10.1016/j.finel.2014.07.002 | - |
dc.identifier.scopus | eid_2-s2.0-84904891369 | - |
dc.identifier.hkuros | 243640 | - |
dc.identifier.volume | 90 | - |
dc.identifier.spage | 113 | - |
dc.identifier.epage | 130 | - |
dc.identifier.isi | WOS:000340990600012 | - |
dc.publisher.place | Netherlands | - |
dc.identifier.issnl | 0168-874X | - |