{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T05:55:12Z","timestamp":1775886912150,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,6,28]],"date-time":"2008-06-28T00:00:00Z","timestamp":1214611200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s00454-008-9094-6","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T13:53:47Z","timestamp":1214574827000},"page":"325-356","source":"Crossref","is-referenced-by-count":27,"title":["Reconstruction Using Witness Complexes"],"prefix":"10.1007","volume":"40","author":[{"given":"Leonidas J.","family":"Guibas","sequence":"first","affiliation":[]},{"given":"Steve Y.","family":"Oudot","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,6,28]]},"reference":[{"issue":"4","key":"9094_CR1","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1007\/PL00009475","volume":"22","author":"N. Amenta","year":"1999","unstructured":"Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22(4), 481\u2013504 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9094_CR2","doi-asserted-by":"crossref","unstructured":"Amenta, N., Choi, S.: One-pass Delaunay filtering for homeomorphic 3D surface reconstruction. Manuscript (1999)","DOI":"10.1145\/336154.336207"},{"key":"9094_CR3","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1142\/S0218195902000773","volume":"12","author":"N. Amenta","year":"2002","unstructured":"Amenta, N., Choi, S., Dey, T.K., Leekha, N.: A simple algorithm for homeomorphic surface reconstruction. Int. J. Comput. Geom. Appl. 12, 125\u2013141 (2002)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9094_CR4","doi-asserted-by":"crossref","unstructured":"Attali, D., Edelsbrunner, H., Mileyko, Y.: Weak witnesses for Delaunay triangulations of submanifolds. In: Proc. ACM Symp. on Solid and Physical Modeling, pp. 143\u2013150 (2007)","DOI":"10.1145\/1236246.1236267"},{"key":"9094_CR5","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0925-7721(01)00018-9","volume":"19","author":"J.-D. Boissonnat","year":"2001","unstructured":"Boissonnat, J.-D., Cazals, F.: Natural neighbor coordinates of points on a surface. Comput. Geom.: Theory Appl. 19, 155\u2013173 (2001)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"9094_CR6","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.-D., Guibas, L.J., Oudot, S.Y.: Manifold reconstruction in arbitrary dimensions using witness complexes. In: Proc. 23rd Symp. on Comput. Geom., pp. 194\u2013203 (2007)","DOI":"10.1145\/1247069.1247106"},{"issue":"5","key":"9094_CR7","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/j.gmod.2005.01.004","volume":"67","author":"J.-D. Boissonnat","year":"2005","unstructured":"Boissonnat, J.-D., Oudot, S.: Provably good sampling and meshing of surfaces. Graph. Models 67(5), 405\u2013451 (2005)","journal-title":"Graph. Models"},{"key":"9094_CR8","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.-D., Oudot, S.: Provably good sampling and meshing of Lipschitz surfaces. In: Proc. 22nd Annu. Symp. Comput. Geom., pp. 337\u2013346 (2006)","DOI":"10.1145\/1137856.1137906"},{"key":"9094_CR9","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/978-3-540-33259-6_6","volume-title":"Effective Computational Geometry for Curves and Surfaces","author":"F. Cazals","year":"2006","unstructured":"Cazals, F., Giesen, J.: Delaunay triangulation based surface reconstruction. In: Boissonnat, J.D., Teillaud, M. (eds.) Effective Computational Geometry for Curves and Surfaces, pp. 231\u2013273. Springer, Berlin (2006)"},{"key":"9094_CR10","doi-asserted-by":"crossref","unstructured":"Chazal, F., Cohen-Steiner, D., Lieutier, A.: A sampling theory for compact sets in Euclidean space. In: Proc. 22nd Annu. Symp. Comput. Geom., pp. 319\u2013326 (2006)","DOI":"10.1145\/1137856.1137904"},{"key":"9094_CR11","unstructured":"Chazal, F., Lieutier, A.: Weak feature size and persistent homology: Computing homology of solids in \u211d n from noisy data samples. Technical Report 378, Institut de Math\u00e9matiques de Bourgogne (2004). Partially published in Proc. 21st Annu. ACM Symp. on Comput. Geom., pp. 255\u2013262 (2005)"},{"issue":"4","key":"9094_CR12","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/j.gmod.2005.01.002","volume":"67","author":"F. Chazal","year":"2005","unstructured":"Chazal, F., Lieutier, A.: The \u03bb-medial axis. Graph. Models 67(4), 304\u2013331 (2005)","journal-title":"Graph. Models"},{"key":"9094_CR13","doi-asserted-by":"crossref","unstructured":"Chazal, F., Lieutier, A.: Topology guaranteeing manifold reconstruction using distance function to noisy data. In: Proc. 22nd Annu. Symp. on Comput. Geom., pp. 112\u2013118 (2006)","DOI":"10.1145\/1137856.1137876"},{"key":"9094_CR14","doi-asserted-by":"crossref","unstructured":"Chazal, F., Oudot, S.Y.: Towards persistence-based reconstruction in Euclidean spaces. In: Proc. 24th ACM Symp. Comput. Geom., pp. 232\u2013241 (2008)","DOI":"10.1145\/1377676.1377719"},{"key":"9094_CR15","unstructured":"Cheng, S.-W., Dey, T.K., Ramos, E.A.: Manifold reconstruction from point samples. In: Proc. 16th Symp. Discrete Algorithms, pp. 1018\u20131027 (2005)"},{"issue":"1\u20132","key":"9094_CR16","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.comgeo.2004.07.004","volume":"31","author":"S.-W. Cheng","year":"2005","unstructured":"Cheng, S.-W., Funke, S., Golin, M., Kumar, P., Poon, S.-H., Ramos, E.: Curve reconstruction from noisy samples. Comput. Geom.: Theory Appl. 31(1\u20132), 63\u2013100 (2005)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"9094_CR17","doi-asserted-by":"crossref","unstructured":"Chew, L.P.: Guaranteed-quality mesh generation for curved surfaces. In: Proc. 9th Annu. ACM Symp. Comput. Geom., pp. 274\u2013280 (1993)","DOI":"10.1145\/160985.161150"},{"key":"9094_CR18","doi-asserted-by":"crossref","first-page":"15","DOI":"10.7551\/mitpress\/4908.003.0005","volume-title":"Nearest-Neighbor Methods for Learning and Vision: Theory and Practice","author":"K.L. Clarkson","year":"2006","unstructured":"Clarkson, K.L.: Nearest-neighbor searching and metric space dimensions. In: Shakhnarovich, G., Darrell, T., Indyk, P. (eds.) Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pp.\u00a015\u201359. MIT Press, Cambridge (2006)"},{"key":"9094_CR19","doi-asserted-by":"crossref","unstructured":"Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. In: Proc. 21st ACM Symp. Comput. Geom., pp. 263\u2013271 (2005)","DOI":"10.1145\/1064092.1064133"},{"key":"9094_CR20","unstructured":"de Silva, V.: A weak definition of Delaunay triangulation. Technical report, Stanford University, October 2003"},{"key":"9094_CR21","author":"V. Silva de","year":"2008","unstructured":"de Silva, V.: A weak characterisation of the Delaunay triangulation. Geom. Dedicata (2008). doi: 10.2007\/s10711-008-9261-1 . Online First","journal-title":"Geom. Dedicata"},{"key":"9094_CR22","unstructured":"de Silva, V., Carlsson, G.: Topological estimation using witness complexes. In: Proc. Symp. Point-Based Graphics, pp. 157\u2013166 (2004)"},{"key":"9094_CR23","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/s00454-002-2838-9","volume":"29","author":"T.K. Dey","year":"2003","unstructured":"Dey, T.K., Giesen, J., Goswami, S., Zhao, W.: Shape dimension and approximation from samples. Discrete Comput. Geom. 29, 419\u2013434 (2003)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20132","key":"9094_CR24","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1016\/j.comgeo.2005.10.006","volume":"35","author":"T.K. Dey","year":"2006","unstructured":"Dey, T.K., Goswami, S.: Provable surface reconstruction from noisy samples. Comput. Geom.: Theory Appl. 35(1\u20132), 124\u2013141 (2006)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"9094_CR25","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. In: Proc. 41st Annu. IEEE Symp. Found. Comput. Sci., pp. 454\u2013463 (2000)","DOI":"10.1109\/SFCS.2000.892133"},{"key":"9094_CR26","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1090\/S0002-9947-1959-0110078-1","volume":"93","author":"H. Federer","year":"1959","unstructured":"Federer, H.: Curvature measures. Trans. Am. Math. Soc. 93, 418\u2013491 (1959)","journal-title":"Trans. Am. Math. Soc."},{"key":"9094_CR27","doi-asserted-by":"crossref","first-page":"192","DOI":"10.2307\/2315138","volume":"75","author":"R.L. Graham","year":"1968","unstructured":"Graham, R.L.: Sets of points with given minimum separation (solution to Problem E1921). Am. Math. Mon. 75, 192\u2013193 (1968)","journal-title":"Am. Math. Mon."},{"key":"9094_CR28","doi-asserted-by":"crossref","unstructured":"Kolluri, R.: Provably good moving least squares. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1008\u20131017 (2005)","DOI":"10.1145\/1198555.1198652"},{"key":"9094_CR29","doi-asserted-by":"crossref","unstructured":"Mederos, B., Amenta, N., Velho, L., de Figueiredo, L.H.: Surface reconstruction for noisy point clouds. In: Proc. 3rd Symp. on Geometry Processing, pp.\u00a053\u201362 (2005)","DOI":"10.1590\/S0104-65002004000100005"},{"issue":"1","key":"9094_CR30","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/s00454-008-9053-2","volume":"39","author":"P. Niyogi","year":"2008","unstructured":"Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom. 39(1), 419\u2013441 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"9094_CR31","unstructured":"Oudot, S., Rineau, L., Yvinec, M.: Meshing volumes with curved boundaries. Eng. Comput. (2008, to appear). Special issue IMR 2005"},{"key":"9094_CR32","unstructured":"Oudot, S.Y.: On the topology of the restricted Delaunay triangulation and witness complex in higher dimensions. Technical report, Stanford University, November 2006. LANL arXiv:0803.1296v1 [cs.CG], http:\/\/arxiv.org\/abs\/0803.1296"},{"key":"9094_CR33","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1002\/mana.19690400110","volume":"40","author":"U. Pirl","year":"1969","unstructured":"Pirl, U.: Der Mindestabstand von n in der Einheitskreisscheibe gelegenen Punkten. Math. Nachr. 40, 111\u2013124 (1969)","journal-title":"Math. Nachr."},{"issue":"5500","key":"9094_CR34","doi-asserted-by":"crossref","first-page":"2323","DOI":"10.1126\/science.290.5500.2323","volume":"290","author":"S.T. Roweis","year":"2000","unstructured":"Roweis, S.T., Saul, L.K.: Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500), 2323\u20132326 (2000)","journal-title":"Science"},{"key":"9094_CR35","unstructured":"Shewchuk, J.R.: What is a good linear element? Interpolation, conditioning, and quality measures. In: Proc. 11th Int. Meshing Roundtable, pp.\u00a0115\u2013126 (2002)"},{"key":"9094_CR36","doi-asserted-by":"crossref","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","volume":"290","author":"J.B. Tenenbaum","year":"2000","unstructured":"Tenenbaum, J.B., de Silva, V., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science 290, 2319\u20132323 (2000)","journal-title":"Science"},{"issue":"2","key":"9094_CR37","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00454-004-1146-y","volume":"33","author":"A. Zomorodian","year":"2005","unstructured":"Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33(2), 249\u2013274 (2005)","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9094-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-008-9094-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9094-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T22:37:35Z","timestamp":1709073455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-008-9094-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,28]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9094"],"URL":"https:\/\/doi.org\/10.1007\/s00454-008-9094-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6,28]]}}}