{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/81994"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/81994","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Sliver -Free Three Dimensional Delaunay Mesh Generation","abstract":"The second algorithm adds points to generate well-shaped meshes. It is based on the following observations. Any tetrahedron will disappear from the Delaunay triangulation if a point is added inside the circumsphere of the tetrahedron. Among the tetrahedra created by inserting this new point there could be tetrahedra with large radius-edge ratios, or slivers, or both. However, the new point is incident to every new tetrahedron. We first eliminate tetrahedra with large radius-edge ratios. We then select the point that avoids creating any small slivers when inserting point inside the circumsphere of slivers. We show that the algorithm will not introduce short edges to the Delaunay triangulation. A simple volume argument implies that the algorithm terminates and generates a well-shaped Delaunay mesh. The generated mesh has a good grading. The number of mesh elements is within a small constant factor of any almost-good mesh for that given domain. We also describe some variations of this refinement-based algorithm. In particular, we show that inserting points near sinks instead of circumcenters of bad tetrahedra also generates sliver-free Delaunay meshes.","abstract_html":"The second algorithm adds points to generate well-shaped meshes. It is based on the following observations. Any tetrahedron will disappear from the Delaunay triangulation if a point is added inside the circumsphere of the tetrahedron. Among the tetrahedra created by inserting this new point there could be tetrahedra with large radius-edge ratios, or slivers, or both. However, the new point is incident to every new tetrahedron. We first eliminate tetrahedra with large radius-edge ratios. We then select the point that avoids creating any small slivers when inserting point inside the circumsphere of slivers. We show that the algorithm will not introduce short edges to the Delaunay triangulation. A simple volume argument implies that the algorithm terminates and generates a well-shaped Delaunay mesh. The generated mesh has a good grading. The number of mesh elements is within a small constant factor of any almost-good mesh for that given domain. We also describe some variations of this refinement-based algorithm. In particular, we show that inserting points near sinks instead of circumcenters of bad tetrahedra also generates sliver-free Delaunay meshes.","abstract_has_math":false,"creators":["Li, Xiangyang"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Shang-Hua Teng"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-25T20:21:22Z","date_published":"2015-09-25T20:21:22Z","updated_at":"2026-07-22T22:26:17Z","subjects":["Computer Science"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI9996652"],"render_values":[{"text":"(MiAaPQ)AAI9996652","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/81994","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Shang-Hua Teng"]},{"key":"dc:creator","label":"Author","values":["Li, Xiangyang"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-25T20:21:22Z","10000-01-01","2001"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/81994","(MiAaPQ)AAI9996652"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The second algorithm adds points to generate well-shaped meshes. It is based on the following observations. Any tetrahedron will disappear from the Delaunay triangulation if a point is added inside the circumsphere of the tetrahedron. Among the tetrahedra created by inserting this new point there could be tetrahedra with large radius-edge ratios, or slivers, or both. However, the new point is incident to every new tetrahedron. We first eliminate tetrahedra with large radius-edge ratios. We then select the point that avoids creating any small slivers when inserting point inside the circumsphere of slivers. We show that the algorithm will not introduce short edges to the Delaunay triangulation. A simple volume argument implies that the algorithm terminates and generates a well-shaped Delaunay mesh. The generated mesh has a good grading. The number of mesh elements is within a small constant factor of any almost-good mesh for that given domain. We also describe some variations of this refinement-based algorithm. In particular, we show that inserting points near sinks instead of circumcenters of bad tetrahedra also generates sliver-free Delaunay meshes.","Made available in DSpace on 2015-09-25T20:21:22Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 9996652.pdf: 5736233 bytes, checksum: 3d6048570f7493f32f586f5c63c4ec8b (MD5) Previous issue date: 2001","Embargo set by: Seth Robbins for item 83275 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","108 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2001."]},{"key":"dc:title","label":"Title","values":["Sliver -Free Three Dimensional Delaunay Mesh Generation"]}]}],"canonical_facts":{"dc:contributor":["Shang-Hua Teng"],"dc:creator":["Li, Xiangyang"],"dc:date":["2015-09-25T20:21:22Z","10000-01-01","2001"],"dc:description":["The second algorithm adds points to generate well-shaped meshes. It is based on the following observations. Any tetrahedron will disappear from the Delaunay triangulation if a point is added inside the circumsphere of the tetrahedron. Among the tetrahedra created by inserting this new point there could be tetrahedra with large radius-edge ratios, or slivers, or both. However, the new point is incident to every new tetrahedron. We first eliminate tetrahedra with large radius-edge ratios. We then select the point that avoids creating any small slivers when inserting point inside the circumsphere of slivers. We show that the algorithm will not introduce short edges to the Delaunay triangulation. A simple volume argument implies that the algorithm terminates and generates a well-shaped Delaunay mesh. The generated mesh has a good grading. The number of mesh elements is within a small constant factor of any almost-good mesh for that given domain. We also describe some variations of this refinement-based algorithm. In particular, we show that inserting points near sinks instead of circumcenters of bad tetrahedra also generates sliver-free Delaunay meshes.","Made available in DSpace on 2015-09-25T20:21:22Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 9996652.pdf: 5736233 bytes, checksum: 3d6048570f7493f32f586f5c63c4ec8b (MD5) Previous issue date: 2001","Embargo set by: Seth Robbins for item 83275 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","108 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2001."],"dc:identifier":["http://hdl.handle.net/2142/81994","(MiAaPQ)AAI9996652"],"dc:language":["eng"],"dc:subject":["Computer Science"],"dc:title":["Sliver -Free Three Dimensional Delaunay Mesh Generation"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:17Z"}