File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Optimal delaunay point insertion

TitleOptimal delaunay point insertion
Authors
KeywordsConvex hull
Delaunay triangulation
Tesselation
Voronoï
Issue Date1996
PublisherJohn Wiley & Sons Ltd. The Journal's web site is located at http://www3.interscience.wiley.com/cgi-bin/jhome/1430
Citation
International Journal For Numerical Methods In Engineering, 1996, v. 39 n. 20, p. 3407-3437 How to Cite?
AbstractAn efficient algorithm for Delaunay triangulation of a given set of points in d dimensions is presented. Various steps of the point insertion algorithm are reviewed and many acceleration procedures are implemented to speed up the triangulation process. New features include the search for a neighbouring point by a layering scheme, locating the containing simplex by a random walk, formulas of important geometrical quantities of a new simplex based on those of an old one, a novel approach in establishing the adjacency relationship using connection matrices. The resulting scheme seems to be one of the fastest triangulation algorithms known, which enables us to generate tetrahedra in ℝ3 with a linear generation rate of 15000 tetrahedra per second for randomly generated points on an HP 735 workstation.
Persistent Identifierhttp://hdl.handle.net/10722/71673
ISSN
2015 Impact Factor: 2.1
2015 SCImago Journal Rankings: 2.007
References

 

DC FieldValueLanguage
dc.contributor.authorBorouchaki, Hen_HK
dc.contributor.authorGeorge, PLen_HK
dc.contributor.authorLo, SHen_HK
dc.date.accessioned2010-09-06T06:34:07Z-
dc.date.available2010-09-06T06:34:07Z-
dc.date.issued1996en_HK
dc.identifier.citationInternational Journal For Numerical Methods In Engineering, 1996, v. 39 n. 20, p. 3407-3437en_HK
dc.identifier.issn0029-5981en_HK
dc.identifier.urihttp://hdl.handle.net/10722/71673-
dc.description.abstractAn efficient algorithm for Delaunay triangulation of a given set of points in d dimensions is presented. Various steps of the point insertion algorithm are reviewed and many acceleration procedures are implemented to speed up the triangulation process. New features include the search for a neighbouring point by a layering scheme, locating the containing simplex by a random walk, formulas of important geometrical quantities of a new simplex based on those of an old one, a novel approach in establishing the adjacency relationship using connection matrices. The resulting scheme seems to be one of the fastest triangulation algorithms known, which enables us to generate tetrahedra in ℝ3 with a linear generation rate of 15000 tetrahedra per second for randomly generated points on an HP 735 workstation.en_HK
dc.languageengen_HK
dc.publisherJohn Wiley & Sons Ltd. The Journal's web site is located at http://www3.interscience.wiley.com/cgi-bin/jhome/1430en_HK
dc.relation.ispartofInternational Journal for Numerical Methods in Engineeringen_HK
dc.rightsInternational Journal for Numerical Methods in Engineering. Copyright © John Wiley & Sons Ltd.en_HK
dc.subjectConvex hullen_HK
dc.subjectDelaunay triangulationen_HK
dc.subjectTesselationen_HK
dc.subjectVoronoïen_HK
dc.titleOptimal delaunay point insertionen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0029-5981&volume=39&spage=3407 &epage= 3437&date=1996&atitle=Optimal+Delaunay+point+insertionen_HK
dc.identifier.emailLo, SH:hreclsh@hkucc.hku.hken_HK
dc.identifier.authorityLo, SH=rp00223en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-0030269931en_HK
dc.identifier.hkuros42447en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0030269931&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume39en_HK
dc.identifier.issue20en_HK
dc.identifier.spage3407en_HK
dc.identifier.epage3437en_HK
dc.publisher.placeUnited Kingdomen_HK
dc.identifier.scopusauthoridBorouchaki, H=7003830832en_HK
dc.identifier.scopusauthoridGeorge, PL=7202720451en_HK
dc.identifier.scopusauthoridLo, SH=7401542444en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats