{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:12:22Z","timestamp":1767139942608,"version":"build-2238731810"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100006234","name":"Sandia National Laboratories","doi-asserted-by":"publisher","award":["Laboratory Directed Research and Development (LDRD)"],"award-info":[{"award-number":["Laboratory Directed Research and Development (LDRD)"]}],"id":[{"id":"10.13039\/100006234","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1566137"],"award-info":[{"award-number":["1566137"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00454-017-9901-z","type":"journal-article","created":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T09:54:26Z","timestamp":1497866066000},"page":"946-985","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Avoiding the Global Sort: A Faster Contour Tree Algorithm"],"prefix":"10.1007","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6584-4843","authenticated-orcid":false,"given":"Benjamin","family":"Raichel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"9901_CR1","doi-asserted-by":"crossref","unstructured":"Bajaj, C., van Kreveld, M., van Oostrum, R., Pascucci, V., Schikore, D.R.: Contour trees and small seed sets for isosurface traversal. Department of Information and Computing Sciences, Utrecht University (1998). http:\/\/www.cs.uu.nl\/research\/techreps\/repo\/CS-1998\/1998-25.pdf","DOI":"10.1145\/262839.269238"},{"key":"9901_CR2","doi-asserted-by":"crossref","unstructured":"Beketayev, K., Weber, G.H., Haranczyk, M., Bremer, P.-T., Hlawitschka, M., Hamann, B.: Topology-based visualization of transformation pathways in complex chemical systems. In: Hauser, H. et al. (eds.) Proceedings of the 13th Eurographics\/IEEE\u2014VGTC Conference on Visualization (EuroVis\u201911), pp. 663\u2013672. The Eurographs Association (2011)","DOI":"10.1111\/j.1467-8659.2011.01915.x"},{"key":"9901_CR3","doi-asserted-by":"crossref","unstructured":"Boyell, R.L., Ruston, H.: Hybrid techniques for real-time radar simulation. In: Proceedings of the Fall Joint Computer Conference (AFIPS\u201963), pp. 445\u2013458. ACM, New York (1963)","DOI":"10.1145\/1463822.1463869"},{"issue":"2","key":"9901_CR4","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1109\/TVCG.2009.69","volume":"16","author":"P-T Bremer","year":"2010","unstructured":"Bremer, P.-T., Weber, G., Pascucci, V., Day, M., Bell, J.: Analyzing and tracking burning structures in lean premixed hydrogen flames. IEEE Trans. Vis. Comput. Graph. 16(2), 248\u2013260 (2010)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"9","key":"9901_CR5","doi-asserted-by":"publisher","first-page":"1307","DOI":"10.1109\/TVCG.2010.253","volume":"17","author":"P-T Bremer","year":"2011","unstructured":"Bremer, P.-T., Weber, G., Tierny, J., Pascucci, V., Day, M., Bell, J.: Interactive exploration and analysis of large-scale simulations using topology-based data segmentation. IEEE Trans. Vis. Comput. Graph. 17(9), 1307\u20131324 (2011)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"9901_CR6","unstructured":"Carr, H.: Topological Manipulation of isosurfaces. PhD thesis, University of British Columbia (2004)"},{"issue":"2","key":"9901_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0925-7721(02)00093-7","volume":"24","author":"H Carr","year":"2003","unstructured":"Carr, H., Snoeyink, J., Axen, U.: Computing contour trees in all dimensions. Comput. Geom. 24(2), 75\u201394 (2003)","journal-title":"Comput. Geom."},{"issue":"2","key":"9901_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.comgeo.2004.05.002","volume":"30","author":"Y-J Chiang","year":"2005","unstructured":"Chiang, Y.-J., Lenz, T., Lu, X., Rote, G.: Simple and optimal output-sensitive construction of contour trees using monotone paths. Comput. Geom. 30(2), 165\u2013195 (2005)","journal-title":"Comput. Geom."},{"key":"9901_CR9","doi-asserted-by":"crossref","unstructured":"Cole-McLaughlin, K., Edelsbrunner, H., Harer, J., Natarajan, V., Pascucci, V.: Loops in Reeb graphs of 2-manifolds. In: Proceedings of the 19th Annual Symposium on Computational Geometry (SCG\u201903), pp. 344\u2013350. ACM, New York (2003)","DOI":"10.1145\/777792.777844"},{"issue":"6\u20137","key":"9901_CR10","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1016\/j.comgeo.2008.12.003","volume":"42","author":"H Doraiswamy","year":"2009","unstructured":"Doraiswamy, H., Natarajan, V.: Efficient algorithms for computing Reeb graphs. Comput. Geom. 42(6\u20137), 606\u2013616 (2009)","journal-title":"Comput. Geom."},{"issue":"2","key":"9901_CR11","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1109\/TVCG.2012.115","volume":"19","author":"H Doraiswamy","year":"2013","unstructured":"Doraiswamy, H., Natarajan, V.: Computing Reeb graphs as a union of contour trees. IEEE Trans. Vis. Comput. Graph. 19(2), 249\u2013262 (2013)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"9901_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10. Springer, Berlin (1987)"},{"key":"9901_CR13","volume-title":"Computational Topology","author":"H Edelsbrunner","year":"2010","unstructured":"Edelsbrunner, H., Harer, J.L.: Computational Topology. American Mathematical Society, Providence (2010)"},{"issue":"1","key":"9901_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0016-0032(67)90568-6","volume":"284","author":"H Freeman","year":"1967","unstructured":"Freeman, H.: On searching a contour map for a given terrain elevation profile. J. Franklin Inst. 284(1), 1\u201325 (1967)","journal-title":"J. Franklin Inst."},{"key":"9901_CR15","doi-asserted-by":"crossref","unstructured":"Harvey, W., Wang, Y., Wenger, R.: A randomized $${O}(m \\log m)$$ time algorithm for computing Reeb graph of arbitrary simplicial complexes. In: Proceedings of the 26th Annual Symposium on Computational Geometry (SoCG\u201910), pp. 267\u2013276. ACM, New York (2010)","DOI":"10.1145\/1810959.1811005"},{"issue":"5","key":"9901_CR16","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1109\/TVCG.2006.186","volume":"12","author":"D Laney","year":"2006","unstructured":"Laney, D., Bremer, P.-T., Macarenhas, A., Miller, P., Pascucci, V.: Understanding the structure of the turbulent mixing layer in hydrodynamic instabilities. IEEE Trans. Vis. Comput. Graph. 12(5), 1053\u20131060 (2006)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"9901_CR17","doi-asserted-by":"crossref","unstructured":"Mascarenhas, A., Grout, R.W., Bremer, P.-T., Hawkes, E.W., Pascucci, V., Chen, J.H.: Topological feature extraction for comparison of terascale combustion simulation data. In: Pascucci, V. et al. (eds.) Topological Methods in Data Analysis and Visualization: Theory, Algorithms, and Applications. Mathematics and Visualization, pp. 229\u2013240. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-15014-2_19"},{"key":"9901_CR18","doi-asserted-by":"crossref","unstructured":"Parsa, S.: A deterministic $${O}(m \\log m)$$ time algorithm for the Reeb graph. In: Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG\u201912), pp. 269\u2013276. ACM, New York (2012)","DOI":"10.1145\/2261250.2261289"},{"key":"9901_CR19","doi-asserted-by":"crossref","unstructured":"Pascucci, V., Cole-McLaughlin, K.: Efficient computation of the topology of level sets. In: IEEE Visualization (VIS\u201902), pp. 187\u2013194 (2002)","DOI":"10.1109\/VISUAL.2002.1183774"},{"issue":"3","key":"9901_CR20","doi-asserted-by":"publisher","first-page":"N58","DOI":"10.1145\/1276377.1276449","volume":"26","author":"V Pascucci","year":"2007","unstructured":"Pascucci, V., Scorzelli, G., Bremer, P.-T., Mascarenhas, A.: Robust on-line computation of Reeb graphs: simplicity and speed. ACM Trans. Graph. 26(3), N58 (2007)","journal-title":"ACM Trans. Graph."},{"issue":"1\u20132","key":"9901_CR21","first-page":"187","volume":"41","author":"JBTM Roerdink","year":"2000","unstructured":"Roerdink, J.B.T.M., Meijster, A.: The watershed transform: definitions, algorithms, and parallelization strategies. Fund. Inform. 41(1\u20132), 187\u2013228 (2000)","journal-title":"Fund. Inform."},{"issue":"6","key":"9901_CR22","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1109\/38.103393","volume":"11","author":"Y Shinagawa","year":"1991","unstructured":"Shinagawa, Y., Kunii, T.: Constructing a Reeb graph automatically from cross sections. IEEE Comput. Graph. Appl. 11(6), 44\u201351 (1991)","journal-title":"IEEE Comput. Graph. Appl."},{"issue":"3","key":"9901_CR23","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"9901_CR24","doi-asserted-by":"crossref","unstructured":"Tarasov, S.P., Vyalyi, M.N.: Construction of contour trees in 3D in $${O}(n \\log n)$$ steps. In: Proceedings of the 14th Annual Symposium on Computational Geometry (SCG\u201998), pp. 68\u201375. ACM, New York (1998)","DOI":"10.1145\/276884.276892"},{"issue":"6","key":"9901_CR25","doi-asserted-by":"publisher","first-page":"1177","DOI":"10.1109\/TVCG.2009.163","volume":"15","author":"J Tierny","year":"2009","unstructured":"Tierny, J., Gyulassy, A., Simon, E., Pascucci, V.: Loop surgery for volumetric meshes: Reeb graphs reduced to contour trees. IEEE Trans. Vis. Comput. Graph. 15(6), 1177\u20131184 (2009)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"9901_CR26","doi-asserted-by":"crossref","unstructured":"van Kreveld, M., van Oostrum, R., Bajaj, C., Pascucci, V., Schikore, D.: Contour trees and small seed sets for isosurface traversal. In: Proceedings of the 13th Annual Symposium on Computational Geometry (SCG\u201997), pp. 212\u2013220. ACM, New York (1997)","DOI":"10.1145\/262839.269238"},{"issue":"4","key":"9901_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/359460.359478","volume":"21","author":"J Vuillemin","year":"1978","unstructured":"Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM 21(4), 309\u2013315 (1978)","journal-title":"Commun. ACM"}],"updated-by":[{"DOI":"10.1007\/s00454-022-00417-5","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000}}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-017-9901-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9901-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9901-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T15:28:27Z","timestamp":1750346907000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-017-9901-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["9901"],"URL":"https:\/\/doi.org\/10.1007\/s00454-017-9901-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"4 August 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2017","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2017","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2022","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00454-022-00417-5","URL":"https:\/\/doi.org\/10.1007\/s00454-022-00417-5","order":8,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}