{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20105"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20105","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Topological modeling with simplicial complexes","abstract":"Simplicial complexes are useful for modeling shape of a discrete geometric domain and for discretizing continuous domains. A geometric triangulation of a point set S is a simplicial complex whose vertex set is contained in S and whose underlying space is the convex hull of S. In this thesis we study different approaches for constructing subcomplexes of a geometric triangulation to obtain a good model of a given domain. The work described in this thesis is about regular triangulations, weighted $\\alpha$-shapes and homeomorphic triangulations.","abstract_html":"Simplicial complexes are useful for modeling shape of a discrete geometric domain and for discretizing continuous domains. A geometric triangulation of a point set S is a simplicial complex whose vertex set is contained in S and whose underlying space is the convex hull of S. In this thesis we study different approaches for constructing subcomplexes of a geometric triangulation to obtain a good model of a given domain. The work described in this thesis is about regular triangulations, weighted <span class=\"etd-inline-math\">&alpha;</span>-shapes and homeomorphic triangulations.","abstract_has_math":true,"creators":["Shah, Nimish Rameshbhai"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Edelsbrunner, Herbert"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:28:56Z","date_published":"2011-05-07T12:28:56Z","updated_at":"2026-07-22T22:25:15Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1994 Shah, Nimish Rameshbhai"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9512544","(UMI)AAI9512544"],"render_values":[{"text":"AAI9512544","href":null,"code":true},{"text":"(UMI)AAI9512544","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20105","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Edelsbrunner, Herbert"]},{"key":"dc:creator","label":"Author","values":["Shah, Nimish Rameshbhai"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:28:56Z","10000-01-01","1994"]},{"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"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1994 Shah, Nimish Rameshbhai"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9512544","(UMI)AAI9512544","http://hdl.handle.net/2142/20105"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Simplicial complexes are useful for modeling shape of a discrete geometric domain and for discretizing continuous domains. A geometric triangulation of a point set S is a simplicial complex whose vertex set is contained in S and whose underlying space is the convex hull of S. In this thesis we study different approaches for constructing subcomplexes of a geometric triangulation to obtain a good model of a given domain. The work described in this thesis is about regular triangulations, weighted $\\alpha$-shapes and homeomorphic triangulations.","We develop the notion of a regular triangulation of a set on n weighted points in general position in $\\IR\\sp{d}$. Regular triangulations generalise Delaunay triangulations, and are related to convex hulls in $\\IR\\sp{d+1}$. We present an efficient randomized incremental algorithm for computing the regular triangulation of a finite weighted point set in $\\IR\\sp{d}$. The expected running time for the worst set of n points in $\\IR\\sp{d}$ is O($n\\log n$ + $n\\sp{\\lceil d/2\\rceil}$). We also discuss some implementation issues related to degenerate point sets.","For $\\alpha$ $\\in$ $\\IR$, a weighted $\\alpha$-shape of a finite set of weighted points in $\\IR\\sp{d}$ is obtained from a subcomplex of the regular triangulation of the point set. Weighted $\\alpha$-shapes are useful for molecular modeling and surface reconstruction. We present a definition for weighted $\\alpha$-shapes that applies to any input, including degenerate data. We also give a straightforward algorithm to compute them.","Finally, we introduce the Delaunay simplicial complex of a point set S restricted by a given topological space, a subset of $\\IR\\sp{d}$. This concept is useful in discretizing continuous domains, especially when the dimension of the domain and the imbedding dimension are different. The restricted Delaunay simplicial complex is a subcomplex of the Delaunay triangulation of S. We present sufficient conditions for the underlying space of the restricted Delaunay simplicial complex to be homeomorphic to the given topological space.","Made available in DSpace on 2011-05-07T12:28:56Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9512544.pdf: 3514755 bytes, checksum: 92974ac470c9cc1b03b87dedcb994a30 (MD5) Previous issue date: 1994","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:41:36Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:18:01-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Topological modeling with simplicial complexes"]}]}],"canonical_facts":{"dc:contributor":["Edelsbrunner, Herbert"],"dc:creator":["Shah, Nimish Rameshbhai"],"dc:date":["2011-05-07T12:28:56Z","10000-01-01","1994"],"dc:description":["Simplicial complexes are useful for modeling shape of a discrete geometric domain and for discretizing continuous domains. A geometric triangulation of a point set S is a simplicial complex whose vertex set is contained in S and whose underlying space is the convex hull of S. In this thesis we study different approaches for constructing subcomplexes of a geometric triangulation to obtain a good model of a given domain. The work described in this thesis is about regular triangulations, weighted $\\alpha$-shapes and homeomorphic triangulations.","We develop the notion of a regular triangulation of a set on n weighted points in general position in $\\IR\\sp{d}$. Regular triangulations generalise Delaunay triangulations, and are related to convex hulls in $\\IR\\sp{d+1}$. We present an efficient randomized incremental algorithm for computing the regular triangulation of a finite weighted point set in $\\IR\\sp{d}$. The expected running time for the worst set of n points in $\\IR\\sp{d}$ is O($n\\log n$ + $n\\sp{\\lceil d/2\\rceil}$). We also discuss some implementation issues related to degenerate point sets.","For $\\alpha$ $\\in$ $\\IR$, a weighted $\\alpha$-shape of a finite set of weighted points in $\\IR\\sp{d}$ is obtained from a subcomplex of the regular triangulation of the point set. Weighted $\\alpha$-shapes are useful for molecular modeling and surface reconstruction. We present a definition for weighted $\\alpha$-shapes that applies to any input, including degenerate data. We also give a straightforward algorithm to compute them.","Finally, we introduce the Delaunay simplicial complex of a point set S restricted by a given topological space, a subset of $\\IR\\sp{d}$. This concept is useful in discretizing continuous domains, especially when the dimension of the domain and the imbedding dimension are different. The restricted Delaunay simplicial complex is a subcomplex of the Delaunay triangulation of S. We present sufficient conditions for the underlying space of the restricted Delaunay simplicial complex to be homeomorphic to the given topological space.","Made available in DSpace on 2011-05-07T12:28:56Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9512544.pdf: 3514755 bytes, checksum: 92974ac470c9cc1b03b87dedcb994a30 (MD5) Previous issue date: 1994","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:41:36Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:18:01-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9512544","(UMI)AAI9512544","http://hdl.handle.net/2142/20105"],"dc:language":["eng"],"dc:rights":["Copyright 1994 Shah, Nimish Rameshbhai"],"dc:subject":["Computer Science"],"dc:title":["Topological modeling with simplicial complexes"],"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:25:15Z"}