{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:49:23Z","timestamp":1753879763948,"version":"3.41.2"},"reference-count":36,"publisher":"ASME International","issue":"1","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,3,1]]},"abstract":"<jats:p>Monotone paths are useful in many engineering design applications. In this paper, we address the problem of answering monotone descent path queries on terrains that are continually changing. A terrain can be represented by a unique contour tree. Such a contour tree belongs to a class of graphs called arbitrarily directed trees (ADTs). Let T be an ADT with n nodes. In this paper, we present a new linear time preprocessing algorithm for decomposing a static ADT T into a forest F, with which we can answer lowest common descendent (LCA) queries in O(1) time. This is useful in answering monotone path queries on the corresponding terrain. We show how to maintain this data structure, and thereby answer LCA queries efficiently, for dynamic ADTs. We also show how to maintain the data structure of dynamic terrains, while simultaneously maintaining the corresponding contour tree. This allows us to efficiently answer monotone path queries between any two points on dynamic terrains.<\/jats:p>","DOI":"10.1115\/1.4025780","type":"journal-article","created":{"date-parts":[[2013,10,22]],"date-time":"2013-10-22T16:31:12Z","timestamp":1382459472000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":0,"title":["Monotone Descent Path Queries on Dynamic Terrains"],"prefix":"10.1115","volume":"14","author":[{"given":"Xiangzhi","family":"Wei","sequence":"first","affiliation":[{"name":"Department of IELM, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ajay","family":"Joneja","sequence":"additional","affiliation":[{"name":"Department of IELM, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaobin","family":"Tian","sequence":"additional","affiliation":[{"name":"School of Mechanical, Electronic and Control Engineering, Beijing Jiaotong University Shangyuancun, Xizhimenwai, Haidian District, Beijing 100044, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yan-An","family":"Yao","sequence":"additional","affiliation":[{"name":"School of Mechanical, Electronic and Control Engineering, Beijing Jiaotong University Shangyuancun, Xizhimenwai, Haidian District, Beijing 100044, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2014,1,29]]},"reference":[{"edition":"3rd ed.","volume-title":"Computational Geometry: Algorithms and Applications","year":"2008","key":"2019100601553477800_B1"},{"issue":"2","key":"2019100601553477800_B2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.comgeo.2006.06.003","article-title":"Shortest Monotone Descent Path Problem in Polyhedral Terrain","volume":"37","year":"2007","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"2","key":"2019100601553477800_B3","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1109\/TVCG.2007.47","article-title":"Topology-Controlled Volume Rendering","volume":"13","year":"2007","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"1","key":"2019100601553477800_B4","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.comgeo.2006.05.009","article-title":"Flexible Isosurfaces: Simplifying and Displaying Scalar Topology Using the Contour Tree","volume":"43","year":"2010","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"3","key":"2019100601553477800_B5","doi-asserted-by":"crossref","first-page":"031002","DOI":"10.1115\/1.3615687","article-title":"On Minimum Link Monotone Path Problems","volume":"11","year":"2011","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"key":"2019100601553477800_B6","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1016\/j.cad.2012.06.005","article-title":"Optimal Uniformly Monotone Partitioning of Polygons With Holes","volume":"44","year":"2012","journal-title":"Comput.-Aided Des."},{"key":"2019100601553477800_B7","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.comgeo.2004.05.002","article-title":"Simple and Optimal Output-Sensitive Construction of Contour Trees Using Monotone Paths","volume":"30","year":"2005","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"13","key":"2019100601553477800_B8","first-page":"031003","article-title":"Adaptive Slicing of Moving Least Squares Surfaces: Toward Direct Manufacturing of Point Set Surfaces","volume":"8","year":"2008","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"3","key":"2019100601553477800_B9","first-page":"221","article-title":"Constructive Heterogeneous Object Modeling Using Signed Approximate Real Distance Functions","volume":"6","year":"2005","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"2","key":"2019100601553477800_B10","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1115\/1.1375816","article-title":"Multi-Direction Slicing for Layered Manufacturing","volume":"1","year":"2001","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"3","key":"2019100601553477800_B11","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1007\/PL00009159","article-title":"Trekking in the Alps Without Freezing or Getting Tired","volume":"18","year":"1997","journal-title":"Algorithmica"},{"key":"2019100601553477800_B12","doi-asserted-by":"crossref","unstructured":"van Kreveld, M., van Oostrum, R., Bajaj, C., Pascucci, V., and Schikore, D. R., 1997, \u201cContour Trees and Small Seed Sets for Isosurface Traversal,\u201d Proceedings of the 13th Annual Symposium on Computational Geometry, pp. 212\u2013220.","DOI":"10.1145\/262839.269238"},{"issue":"1","key":"2019100601553477800_B13","doi-asserted-by":"crossref","first-page":"011007","DOI":"10.1115\/1.3569830","article-title":"Creeping Contours: A Multilabel Image Segmentation Method for Extracting Boundary Surfaces of Parts in Volumetric Images","volume":"11","year":"2011","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"key":"2019100601553477800_B14","doi-asserted-by":"crossref","unstructured":"Sarkar, R., Zhu, X., Gao, J., Guibas, L. J., and Mitchell, J. S. B., 2008, \u201cIsocontour Queries and Gradient Descent With Guaranteed Delivery in Sensor Networks,\u201d Proceedings of the 27th Annual IEEE Conference on Computer Communications, pp. 1175\u20131183.","DOI":"10.1109\/INFOCOM.2007.149"},{"issue":"6","key":"2019100601553477800_B15","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0020-0190(94)00050-6","article-title":"Finding Lowest Common Ancestors in Arbitrarily Directed Trees","volume":"50","year":"1994","journal-title":"Inf. Process. Lett."},{"key":"2019100601553477800_B16","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1145\/1039488.1039493","article-title":"Compact Oracles for Reachability and Approximate Distances in Planar Digraphs","volume":"51","year":"2004","journal-title":"J. ACM"},{"issue":"2","key":"2019100601553477800_B17","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","article-title":"Lowest Common Ancestors in Trees and Directed Acyclic Graphs","volume":"57","year":"2005","journal-title":"J. Algorithms"},{"key":"2019100601553477800_B18","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/s00224-004-1155-5","article-title":"Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment","volume":"37","year":"2004","journal-title":"Theory Comput. Syst."},{"key":"2019100601553477800_B19","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","article-title":"Fast Algorithms for Finding Nearest Common Ancestor","volume":"13","year":"1984","journal-title":"SIAM J. Sci. Comput."},{"key":"2019100601553477800_B20","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","article-title":"On Finding Lowest Common Ancestors: Simplification and Parallelization","volume":"17","year":"1988","journal-title":"SIAM J. Sci. Comput."},{"key":"2019100601553477800_B21","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","article-title":"Finding Level Ancestors in Trees","volume":"48","year":"1994","journal-title":"J. Comput. Syst. Sci."},{"key":"2019100601553477800_B22","doi-asserted-by":"crossref","unstructured":"Bender, M., and Farach-Colton, M., 2000, \u201cThe LCA Problem Revisited,\u201d Proceedings of Latin American Theoretical Informatics, pp. 88\u201394.","DOI":"10.1007\/10719839_9"},{"key":"2019100601553477800_B23","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","article-title":"A Data Structure for Dynamic Trees","volume":"26","year":"1983","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"2019100601553477800_B24","doi-asserted-by":"crossref","first-page":"894","DOI":"10.1137\/S0097539700370539","article-title":"Dynamic LCA Queries on Trees","volume":"34","year":"2005","journal-title":"SIAM J. Sci. Comput."},{"key":"2019100601553477800_B25","unstructured":"Gabow, H. N., 1990, \u201cData Structure for Weighted Matching and Nearest Common Ancestors With Linking,\u201d Proceedings of the 1st Annual ACM Symposium on Discrete Algorithms, pp. 434\u2013443."},{"key":"2019100601553477800_B26","doi-asserted-by":"crossref","unstructured":"Eckhardt, S., M\u00fchling, A., and Nowak, J., 2007, \u201cFast Lowest Common Ancestor Computations in Dags,\u201d Proceedings of the 15th Annual European Conference on Algorithms, pp. 705\u2013716.","DOI":"10.1007\/978-3-540-75520-3_62"},{"key":"2019100601553477800_B27","unstructured":"Rebane, G., and Pearl, J., 1987, \u201cThe Recovery of Causal Poly-Trees From Statistical Data,\u201d Proceedings of the 3rd Workshop Uncertainty in Artificial Intelligence, pp. 222\u2013228."},{"key":"2019100601553477800_B28","unstructured":"Kim, J. H., and Pearl, J., 1983, \u201cA Computational Model for Causal and Diagnostic Reasoning in Inference Engines,\u201d Proceedings of the 8th International Joint Conference on Artificial Intelligencepp. 190\u2013193."},{"key":"2019100601553477800_B29","unstructured":"Lai, K. J., 2008, \u201cComplexity of Union-Split-Find Problems,\u201d M.S. thesis, Massachusetts Institute of Technology, Erik Demaine, Adviser."},{"key":"2019100601553477800_B30","doi-asserted-by":"crossref","unstructured":"Patrascu, M., and Demaine, E. D., 2004, \u201cLower Bounds for Dynamic Connectivity,\u201d Proceedings of the 36th ACM symposium on Theory of Computing, pp. 546\u2013553.","DOI":"10.1145\/1007352.1007435"},{"issue":"2","key":"2019100601553477800_B31","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0925-7721(02)00093-7","article-title":"Computing Contour Trees in all Dimensions","volume":"24","year":"2003","journal-title":"Comput. Geom.: Theory Appl."},{"key":"2019100601553477800_B32","unstructured":"Pascucci, V., 2001, \u201cOn the Topology of the Level Sets of a Scalar Field,\u201d Proceedings the 13th Canadian Conference on Computational Geometry, pp. 141\u2013144."},{"issue":"3","key":"2019100601553477800_B33","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.comgeo.2007.11.001","article-title":"Time-Varying Reeb Graphs for Continuous Space-Time Data","volume":"41","year":"2008","journal-title":"Comput. Geom.: Theory Appl."},{"key":"2019100601553477800_B34","first-page":"35","article-title":"Jacobi Sets of Multiple Morse Functions","volume-title":"Foundations of Computational Mathematics","year":"2002"},{"key":"2019100601553477800_B35","doi-asserted-by":"crossref","unstructured":"Mascarenhaus, A., and Snoeyink, J., 2005, \u201cImplementing Time-Varying Contour Trees,\u201d Proceedings of the 21st Annual Symposium on Computational Geometry, pp. 370\u2013371.","DOI":"10.1145\/1064092.1064151"},{"issue":"1","key":"2019100601553477800_B36","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","article-title":"Optimal Search in Planar Subdivisions","volume":"12","year":"1983","journal-title":"SIAM J. Sci. Comput."}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4025780\/6099765\/jcise_014_01_011008.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4025780\/6099765\/jcise_014_01_011008.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,6]],"date-time":"2019-10-06T05:56:08Z","timestamp":1570341368000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.4025780\/370124\/Monotone-Descent-Path-Queries-on-Dynamic-Terrains"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,29]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,3,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4025780","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2014,1,29]]},"article-number":"011008"}}