Loading…
An Obstruction to Delaunay Triangulations in Riemannian Manifolds
Delaunay has shown that the Delaunay complex of a finite set of points P of Euclidean space R m triangulates the convex hull of P , provided that P satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay’s gen...
Saved in:
| Published in: | Discrete & computational geometry 2018, Vol.59 (1), p.226-237 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c359t-de42f03dd32c3b14362f44d91a7aacde434c67c1985d180ff3e2e038f3c6a46e3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c359t-de42f03dd32c3b14362f44d91a7aacde434c67c1985d180ff3e2e038f3c6a46e3 |
| container_end_page | 237 |
| container_issue | 1 |
| container_start_page | 226 |
| container_title | Discrete & computational geometry |
| container_volume | 59 |
| creator | Boissonnat, Jean-Daniel Dyer, Ramsay Ghosh, Arijit Martynchuk, Nikolay |
| description | Delaunay has shown that the Delaunay complex of a finite set of points
P
of Euclidean space
R
m
triangulates the convex hull of
P
,
provided that
P
satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay’s genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on
P
are required. A natural one is to assume that
P
is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2. |
| doi_str_mv | 10.1007/s00454-017-9908-5 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_1978212633</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1978212633</sourcerecordid><originalsourceid>FETCH-LOGICAL-c359t-de42f03dd32c3b14362f44d91a7aacde434c67c1985d180ff3e2e038f3c6a46e3</originalsourceid><addsrcrecordid>eNp1kM1LAzEQxYMoWKt_gLeA5-gkk_3IsdRPqBSknkOaTcqWbbYmuwf_e1PWgxdPA_N-783wCLnlcM8BqocEIAvJgFdMKahZcUZmXKJgIKU8J7MsKFZgVV6Sq5T2kPGMzchiEeh6m4Y42qHtAx16-ug6MwbzTTexNWE3duakJNoG-tG6gwkhr-m7Ca3vuyZdkwtvuuRufuecfD4_bZavbLV-eVsuVsxioQbWOCk8YNOgsLjNr5XCS9kobipjbFZR2rKyXNVFw2vwHp1wgLVHWxpZOpyTuyn3GPuv0aVB7_sxhnxSc1XVgosSMVN8omzsU4rO62NsDyZ-aw761JSemtK5EH1qShfZIyZPymzYufgn-V_TD4wka0Q</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1978212633</pqid></control><display><type>article</type><title>An Obstruction to Delaunay Triangulations in Riemannian Manifolds</title><source>Springer Link</source><creator>Boissonnat, Jean-Daniel ; Dyer, Ramsay ; Ghosh, Arijit ; Martynchuk, Nikolay</creator><creatorcontrib>Boissonnat, Jean-Daniel ; Dyer, Ramsay ; Ghosh, Arijit ; Martynchuk, Nikolay</creatorcontrib><description>Delaunay has shown that the Delaunay complex of a finite set of points
P
of Euclidean space
R
m
triangulates the convex hull of
P
,
provided that
P
satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay’s genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on
P
are required. A natural one is to assume that
P
is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2.</description><identifier>ISSN: 0179-5376</identifier><identifier>EISSN: 1432-0444</identifier><identifier>DOI: 10.1007/s00454-017-9908-5</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Combinatorics ; Computational Mathematics and Numerical Analysis ; Euclidean geometry ; Euclidean space ; Manifolds (mathematics) ; Mathematics ; Mathematics and Statistics ; Riemann manifold ; Theorems ; Triangulation ; Voronoi graphs</subject><ispartof>Discrete & computational geometry, 2018, Vol.59 (1), p.226-237</ispartof><rights>Springer Science+Business Media, LLC 2017</rights><rights>Discrete & Computational Geometry is a copyright of Springer, (2017). All Rights Reserved.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c359t-de42f03dd32c3b14362f44d91a7aacde434c67c1985d180ff3e2e038f3c6a46e3</citedby><cites>FETCH-LOGICAL-c359t-de42f03dd32c3b14362f44d91a7aacde434c67c1985d180ff3e2e038f3c6a46e3</cites><orcidid>0000-0001-5083-7181</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Boissonnat, Jean-Daniel</creatorcontrib><creatorcontrib>Dyer, Ramsay</creatorcontrib><creatorcontrib>Ghosh, Arijit</creatorcontrib><creatorcontrib>Martynchuk, Nikolay</creatorcontrib><title>An Obstruction to Delaunay Triangulations in Riemannian Manifolds</title><title>Discrete & computational geometry</title><addtitle>Discrete Comput Geom</addtitle><description>Delaunay has shown that the Delaunay complex of a finite set of points
P
of Euclidean space
R
m
triangulates the convex hull of
P
,
provided that
P
satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay’s genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on
P
are required. A natural one is to assume that
P
is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2.</description><subject>Combinatorics</subject><subject>Computational Mathematics and Numerical Analysis</subject><subject>Euclidean geometry</subject><subject>Euclidean space</subject><subject>Manifolds (mathematics)</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Riemann manifold</subject><subject>Theorems</subject><subject>Triangulation</subject><subject>Voronoi graphs</subject><issn>0179-5376</issn><issn>1432-0444</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><recordid>eNp1kM1LAzEQxYMoWKt_gLeA5-gkk_3IsdRPqBSknkOaTcqWbbYmuwf_e1PWgxdPA_N-783wCLnlcM8BqocEIAvJgFdMKahZcUZmXKJgIKU8J7MsKFZgVV6Sq5T2kPGMzchiEeh6m4Y42qHtAx16-ug6MwbzTTexNWE3duakJNoG-tG6gwkhr-m7Ca3vuyZdkwtvuuRufuecfD4_bZavbLV-eVsuVsxioQbWOCk8YNOgsLjNr5XCS9kobipjbFZR2rKyXNVFw2vwHp1wgLVHWxpZOpyTuyn3GPuv0aVB7_sxhnxSc1XVgosSMVN8omzsU4rO62NsDyZ-aw761JSemtK5EH1qShfZIyZPymzYufgn-V_TD4wka0Q</recordid><startdate>2018</startdate><enddate>2018</enddate><creator>Boissonnat, Jean-Daniel</creator><creator>Dyer, Ramsay</creator><creator>Ghosh, Arijit</creator><creator>Martynchuk, Nikolay</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7TB</scope><scope>7XB</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FR3</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>KR7</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0N</scope><scope>M2O</scope><scope>M2P</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PADUT</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>Q9U</scope><orcidid>https://orcid.org/0000-0001-5083-7181</orcidid></search><sort><creationdate>2018</creationdate><title>An Obstruction to Delaunay Triangulations in Riemannian Manifolds</title><author>Boissonnat, Jean-Daniel ; Dyer, Ramsay ; Ghosh, Arijit ; Martynchuk, Nikolay</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c359t-de42f03dd32c3b14362f44d91a7aacde434c67c1985d180ff3e2e038f3c6a46e3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Combinatorics</topic><topic>Computational Mathematics and Numerical Analysis</topic><topic>Euclidean geometry</topic><topic>Euclidean space</topic><topic>Manifolds (mathematics)</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Riemann manifold</topic><topic>Theorems</topic><topic>Triangulation</topic><topic>Voronoi graphs</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Boissonnat, Jean-Daniel</creatorcontrib><creatorcontrib>Dyer, Ramsay</creatorcontrib><creatorcontrib>Ghosh, Arijit</creatorcontrib><creatorcontrib>Martynchuk, Nikolay</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical & Transportation Engineering Abstracts</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science & Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies & Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>Engineering Research Database</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer science database</collection><collection>Civil Engineering Abstracts</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Computing Database</collection><collection>ProQuest research library</collection><collection>Science Database</collection><collection>Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>ProQuest advanced technologies & aerospace journals</collection><collection>ProQuest Advanced Technologies & Aerospace Collection</collection><collection>Research Library China</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection><collection>ProQuest Central Basic</collection><jtitle>Discrete & computational geometry</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Boissonnat, Jean-Daniel</au><au>Dyer, Ramsay</au><au>Ghosh, Arijit</au><au>Martynchuk, Nikolay</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>An Obstruction to Delaunay Triangulations in Riemannian Manifolds</atitle><jtitle>Discrete & computational geometry</jtitle><stitle>Discrete Comput Geom</stitle><date>2018</date><risdate>2018</risdate><volume>59</volume><issue>1</issue><spage>226</spage><epage>237</epage><pages>226-237</pages><issn>0179-5376</issn><eissn>1432-0444</eissn><abstract>Delaunay has shown that the Delaunay complex of a finite set of points
P
of Euclidean space
R
m
triangulates the convex hull of
P
,
provided that
P
satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay’s genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on
P
are required. A natural one is to assume that
P
is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s00454-017-9908-5</doi><tpages>12</tpages><orcidid>https://orcid.org/0000-0001-5083-7181</orcidid><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0179-5376 |
| ispartof | Discrete & computational geometry, 2018, Vol.59 (1), p.226-237 |
| issn | 0179-5376 1432-0444 |
| language | eng |
| recordid | cdi_proquest_journals_1978212633 |
| source | Springer Link |
| subjects | Combinatorics Computational Mathematics and Numerical Analysis Euclidean geometry Euclidean space Manifolds (mathematics) Mathematics Mathematics and Statistics Riemann manifold Theorems Triangulation Voronoi graphs |
| title | An Obstruction to Delaunay Triangulations in Riemannian Manifolds |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T02%3A28%3A01IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=An%20Obstruction%20to%20Delaunay%20Triangulations%20in%20Riemannian%20Manifolds&rft.jtitle=Discrete%20&%20computational%20geometry&rft.au=Boissonnat,%20Jean-Daniel&rft.date=2018&rft.volume=59&rft.issue=1&rft.spage=226&rft.epage=237&rft.pages=226-237&rft.issn=0179-5376&rft.eissn=1432-0444&rft_id=info:doi/10.1007/s00454-017-9908-5&rft_dat=%3Cproquest_cross%3E1978212633%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c359t-de42f03dd32c3b14362f44d91a7aacde434c67c1985d180ff3e2e038f3c6a46e3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1978212633&rft_id=info:pmid/&rfr_iscdi=true |