Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “iterative refinement”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 145 records · Page 8

Three-Dimensional Heat Flux and Thermal Analysis of Angled Tungsten Samples on DIII-D

ITER-grade tungsten and dispersoid-strengthened tungsten samples with the top surface angled at ~15° towards the incident plasma flux were exposed to 9 H-mode discharges with edge-localized modes (ELMs) in the lower divertor of DIII-D tokamak using the Divertor Material Evaluation System (DiMES). Surface damage included cracking and flaking of material on the two samples farthest away from the plasma strike point, and significant melting of the two samples closest to the strike point. Heat flux and thermal analysis tools new to DIII-D have been applied to better understand this material response and to help optimize the exposure conditions for future experiments. SMITER field-line tracing simulations based on IRTV data and EFIT equilibria estimate an average inter-ELM perpendicular heat flux, 𝑞⊥,𝑖nter−𝐸LM , on the angled surfaces of 10.1 – 19.6 MW/m² for a majority of the 9 discharges, increasing to 15.6 – 24.5 MW/m² for the single, higher-power shot where samples melted. Fast camera data showed shallow intra-ELM melting and re-solidification, which transitioned to bulk inter-ELM melting with melt motion in the 𝐽⃗ 𝑥 𝐵⃗ direction. About 50% of the protruding volume of the most affected sample was displaced via melt-motion. SIERRA thermal modeling software was able to reproduce an onset time of melting consistent with fast camera data and final sample conditions, within < 200 ms. Maximum surface temperatures of 3122 K and 2787 K are estimated for the samples farthest away from the strike point, while the closest samples achieve melting at 4067 ms and 4750 ms into the ~5000 ms plasma exposure. A +10% increase in both the SMITER 𝑞⊥,𝑖nter−𝐸LM calculations and the estimated ELM heat loads 𝑞⊥, 𝐸LM was required to achieve this result, which is within the uncertainty of the diagnostic data but likely accounts for non-ideal geometry effects plus other physics uncertainties not included in this first iteration of modeling. This work provided valuable estimates of the 3D temperature evolution to help better understand the observed surface morphology and internal recrystallization of samples, which are discussed in detail in a complementary manuscript [1]. Benchmarking efforts with more diagnosed DIII-D experiments are underway to further refine the SMITER and SIERRA models for DiMES. Future use of these tools will enable researchers to precisely target heat flux exposure conditions in DIII-D to test, but not exceed, the thermomechanical limitations of novel plasma-facing materials.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Progressive Dynamics for Cloth and Shell Animation

We propose Progressive Dynamics, a coarse-to-fine, level-of-detail simulation method for the physics-based animation of complex frictionally contacting thin shell and cloth dynamics. Progressive Dynamics provides tight-matching consistency and progressive improvement across levels, with comparable quality and realism to high-fidelity, IPC-based shell simulations [Li et al. 2021] at finest resolutions. Together these features enable an efficient animation-design pipeline with predictive coarse-resolution previews providing rapid design iterations for a final, to-be-generated, high-resolution animation. In contrast, previously, to design such scenes with comparable dynamics would require prohibitively slow design iterations via repeated direct simulations on high-resolution meshes. We evaluate and demonstrate Progressive Dynamics's features over a wide range of challenging stress-tests, benchmarks, and animation design tasks. Here Progressive Dynamics efficiently computes consistent previews at costs comparable to coarsest-level direct simulations. Its matching progressive refinements across levels then generate rich, high-resolution animations with high-speed dynamics, impacts, and the complex detailing of the dynamic wrinkling, folding, and sliding of frictionally contacting thin shells and fabrics.

Computer Science↗

Energy Storage Impacts in Resilience Hubs and Other Critical Infrastructure: An Assessment Guide for Developers and Practitioners

Battery energy storage systems (BESS) deployed behind the meter at resilience hubs and other critical infrastructure can provide economic and operational value during normal operations—such as lower and more predictable energy costs—as well as resilience and security benefits during power disruptions by maintaining essential services. However, existing evaluation approaches tend to focus narrowly on engineering performance or rely on broad socio-economic frameworks that are not well suited to behind-the-meter storage. As a result, developers, utilities, and funders often lack consistent methods for defining success, quantifying benefits, and comparing outcomes across projects. This report presents a practitioner-oriented impact assessment framework for evaluating behind-the-meter BESS at resilience hubs and critical infrastructure facilities. The framework is organized into five iterative components—developing an action plan, defining project goals, identifying metrics, collecting data and measuring outcomes, and reporting and using results—and includes a structured metric architecture spanning six impact categories. Designed for real-world constraints such as limited staffing and uneven data availability, the framework was developed, applied, and refined through real projects, and is illustrated with case studies across diverse deployment contexts.

Impact Assessment↗

Multi‐Scale Seismic Imaging of the Ridgecrest, CA, Region With Waveform Inversion of Regional and Dense Array Data

Abstract We develop an inversion procedure for deriving multi‐scale velocity models with waveform inversions of earthquake and ambient noise data at multi‐frequency bands recorded by regional and dense sensor configurations. The method is applied for the area around the 2019 Ridgecrest earthquake rupture zones, utilizing data recorded by regional stations and dense 2D and 1D arrays with station spacings of ∼5 km and ∼100 m, respectively. Starting with regional Vp, Vs models and locations of Ridgecrest aftershocks, the velocity models and event locations are improved iteratively by inversions of waveforms recorded by regional stations and the 2D array, using a minimum spectral element size of ∼600 m. Waveforms from local events recorded by dense 1D arrays across the M7.1 rupture zone with frequencies of up to 10 Hz are used to resolve small‐scale features of the rupture zone and shallow crust with a local spectral element size of 80 m. The refined models provide self‐consistent descriptions of the rupture zone and the shallow crust embedded in the regional structures. The results reveal pronounced low Vs and high Vp/Vs in the M6.4 and M7.1 rupture zones coinciding with concentrations of seismicity, and also around the Garlock fault and in several local basins. We also observe clear velocity contrasts across the Garlock fault with polarity reversals along strike and with depth. The obtained multi‐scale velocity models can be used to improve derivations of earthquake source properties, simulations of dynamic ruptures and ground motions, and the understanding of fault and tectonic processes in the region.

Geochemistry & Geophysics↗

PSTN-056: Survey Cadence Optimization Committee's Phase 3 Recommendations

We present the final planned comprehensive recommendation for Rubin Observatory the Legacy Survey of Space and Time (LSST) survey strategy ahead of the start of LSST. This recommendation is the product of a many-years-long iterative process where community recommendations to maximize the scientific impact of LSST across domains of astrophysics were reviewed, synthesized, aggregated, and merged to define the overall plan for 10 years of LSST observations. The current recommendation builds on Phase 1 (PSTN-053) and Phase 2 recommendations (PSTN-055) and, together, they define a 10-year plan for observing. Here we answer questions left open in PSTN-055, refine additional survey details, and describe the scope of future activities of the SCOC.

79 ASTRONOMY AND ASTROPHYSICS↗

Multiscale Molecular Dynamics Simulations: Accelerating Conformational Sampling of Biomolecular Systems by Iterating All-Atom and Coarse-Grained Simulations

We developed the atomistic-coarse-grained multiscale MD simulation method in the OpenMM simulation package by iterating between the all-atom (AA) and coarse-grained (CG) MD simulations to enhance the sampling of biomolecular conformations. As the free energy surfaces are flattened during CG MD simulations, we can accelerate the transitions between different low-energy conformations. The AA-CG-AA cycles are repeated, facilitating the accelerated sampling of biomolecular conformations at a CG level, while the finer atomistic interactions are refined with AA simulators.

Do, Hung Nguyen↗

Extended Finite Element Based Approach in Additive Manufacturing Modeling for Optimizing Highly Complex Manifold in Protonic Ceramic Electrochemical Cells

The objective of this project is to develop a novel numerical approach based on the extended finite element method (XFEM) for modeling moving boundaries of material deposited in additive manufacturing (AM) process with improved accuracy and reduced computational cost. One of the major challenges in simulating AM processes is that the boundaries of the computational domain need to change as material is deposited. Previous approaches have achieved this by activating new finite elements, but this requires a high level of mesh refinement to capture small movement of the boundary. XFEM allows the solution boundary to move independently of the mesh, permitting smooth representation of the evolution of the boundary as material is deposited. As a result, this new method will significantly improve the simulation accuracy while reducing the computational cost compared with existing approaches. Furthermore, this project will bring significant improvements for the design and AM process optimization in an iterative fashion among numerical simuation, parameter optimization, and experimental validation. Specifically, this project will support the protonic ceramic electrochemical cells (PCEC) stack development at INL by providing insights into the density, residual stress, thermal and mechanical properties of the PCEC manifold and interconnect, which is critical in enhancing the system lifetime and reducing the overall cost. Upon the success of proposed development and validation of the proposed approach, simulation will be applied to determine an optimal set of AM process parameters for the PCEC manifold production. This project will consolidate Idaho National Laboratory (INL)’s simulation capabilities provided by the MOOSE framework and the Valhalla AM simulation application, with encouraging expansion to emerging PCEC applications and AM technologies at INL and beyond.

97 MATHEMATICS AND COMPUTING↗

Validation of LOCA2 and STAR-ESDM Statistically Downscaled Products

The National Climate Assessment (NCA) is the preeminent national report examining current and future risks posed by climate change. Countless agencies, policymakers, stakeholders and other end-users rely upon guidance from the NCA to plan for an uncertain future. These groups all depend on modern curated data, provided alongside the NCA, to quantify the impact of climate change on metrics of relevance for their decision processes. In its fifth iteration (NCA5), two statistically downscaled ensemble products, each providing data at grid spacing of approximately 5km over the contiguous United States, were selected to accompany the report. These include LOCalized Analogs version 2 (LOCA2) and Seasonal Trends and Analysis of Residuals Empirical-Statistical Downscaling Model (STAR-ESDM). Both data products are produced through a process known as statistical downscaling, where relatively coarse Global Climate Model (GCM) data is refined to locally relevant scales through the application of scientifically-supported empirical and algorithmic relationships. In support of the NCA effort, this report provides an independent validation of these two products against historical observations, with a focus on precipitation and near-surface temperature variables. Based on the results of this validation, several recommendations are provided related to the use of these data products. The structure of this report is as follows: In section 2, we review three gridded observational products that are used as part of our intercomparison. In section 3, we describe the two statistical downscaling techniques and their corresponding datasets that are the focus of this study. In section 4, the methodology we employ for validation is described. Section 5 provides results of the validation, which in turn motivate our recommendations on the use of these data products. A brief summary is provided in section 6.

54 ENVIRONMENTAL SCIENCES↗

Recent Progress of JT-60SA Project toward Plasma Operation

Superconducting tokamak JT-60SA plays an essential role in fusion research and development by supporting and complementing ITER project, providing directions to the DEMO design activity and fostering next generation scientists and engineers. Since the incident of the Equilibrium Field coil #1 during the Integrated Commissioning (IC) in March 2021, both EU and JA Implementing agencies (IAs) have examined how to ensure safety operation of JT-60SA by mitigating the risk of possible discharge occurrence inside the cryostat. Based on the experience of the Global Paschen tests, the IAs have established a strategy of risk mitigation measures, which is a combination of (i) reinforcement of insulation, (ii) avoiding unnecessary voltage application to the coil systems and (iii) immediate de-energization of the coils when deteriorated vacuum condition is detected. Thanks to the considerable efforts of the Integrated Project Team (IPT) members, the IC restarted in May 2023. After the confirmation of superconducting state of coil systems (TF, EF and CS), the coil energization test and the plasma operation (OP-1) starts. The first plasma was successfully achieved on 23 October 2023 with a limited value of applied voltage and current to the coils. The plasma configuration control will be also confirmed with low plasma current and low auxiliary heating power conditions. Based on the IO-F4E-QST collaboration, activities of JT-60SA have been shared with the IO and provided an important lesson learned for ITER assembly and commissioning, and will provide an outstanding contribution to fusion research at large. After OP-1, Maintenance & Enhancement phase 1 (M/E-1) starts from January 2024, in which in-vessel components are installed, and heating system and diagnostic system are extensively upgraded to allow high power heating experiment planned in OP-2. In order to make the best use of JT-60SA, newly organized JT-60SA experiment team will refine the research plan in the future high heating power operation phase.

Broader Approach activities↗

Determining the Ensemble N -Representability of Reduced Density Matrices

The N-representability problem for reduced density matrices remains a fundamental challenge in electronic structure theory. Following our previous work that employs a unitary-evolution algorithm based on an adaptive derivative-assembled pseudo-Trotter variational quantum algorithm to probe pure-state N-representability of reduced density matrices [J. Chem. Theory Comput. 2024, 20, 9968], in this work we propose a practical framework for determining the ensemble N-representability of a p-body matrix. This is accomplished using a purification strategy that embeds an ensemble state into a pure state defined on an extended Hilbert space, such that the reduced density matrices of the purified state reproduce those of the original ensemble. By iteratively applying variational unitaries to an initial purified state, the proposed algorithm minimizes the Hilbert-Schmidt distance between its p-body reduced density matrix and a specified target p-body matrix, which serves as a measure of the N-representability of the target. This methodology facilitates both error correction of defective ensemble reduced density matrices and quantum-state reconstruction on a quantum computer, offering a route for density-matrix refinement. We validate the algorithm with numerical simulations on systems of two, three, and four electrons in both simple models as well as molecular systems at finite temperature, demonstrating its robustness.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

thornado+FLASH-X: A Hybrid Discontinuous Galerkin–Implicit-explicit and Finite-volume Framework for Neutrino-radiation Hydrodynamics in Core-collapse Supernovae

We present neutrino-transport algorithms implemented in the toolkit for high-order neutrino-radiation hydrodynamics (thornado) and their coupling to self-gravitating hydrodynamics within the adaptive mesh refinement–based multiphysics simulation framework FLASH-X. thornado, developed primarily for simulations of core-collapse supernovae (CCSNe), employs a spectral, six-species two-moment formulation with algebraic closure and special-relativistic observer corrections accurate to $\mathcal{O}(v/c)$, and uses discontinuous Galerkin (DG) methods for phase-space discretization combined with implicit-explicit time stepping. A key development is a nonlinear neutrino–matter coupling algorithm based on nested fixed-point iteration with Anderson acceleration, enabling fully implicit treatment of collisional processes, including energy-coupling interactions such as neutrino–electron scattering and pair production. Coupling to finite-volume (FV) hydrodynamics is achieved through a hybrid DG-FV representation of the fluid variables and operator-split evolution within FLASH-X. The implementation is verified using basic transport tests with idealized opacities and relaxation and deleptonization problems with tabulated microphysics. Spherically symmetric CCSN simulations demonstrate accuracy and robustness of the coupled scheme, including close agreement with the CCSN simulation code Chimera. An axisymmetric CCSN simulation further demonstrates the viability of DG-based neutrino transport for multidimensional supernova modeling within FLASH-X. thornado’s neutrino-transport solver is GPU-enabled using OpenMP offloading or OpenACC, and all CCSN applications included in this work use the GPU implementation. Together, these results establish a foundation for future enhancements in physics fidelity, numerical algorithms, and computational performance, for increasingly realistic large-scale CCSN simulations.

Endeve, Eirik [Oak Ridge National Laboratory (ORNL↗

Area V: Waste Management and Subsurface Science (FY21-23 Final Report)

The objective of the Waste Management and Subsurface Science Topic Area V project is to evaluate the feasibility and safety of an intermediate-depth borehole for disposal of Israel Atomic Energy Commission (IAEC) nuclear waste. The IAEC nuclear waste is currently stored in above ground and/or in near-surface facilities that provide short-term radiological worker safety but do not provide long-term, full security and safeguards protection for the nuclear material. Disposal of the IAEC nuclear waste several hundred meters below the surface in a sealed borehole would provide long-term security and safeguards due to its depth underground, as well as long-term radiological safety, due to its isolation in a stable geological formation. This project supports the nuclear security and safeguards initiatives of the Science and Technology Working Group of the NNSA/IAEC Memorandum of Understanding (MOU) and addresses the Topic Area V objective and associated goals. The goals for Topic Area V are: (1) Assess the suitability of the vadose zone in the Yamin Plain of the northern Negev Desert, Israel as a host location for intermediate-depth borehole disposal of radioactive waste, (2) Define and refine the necessary characterization needs to better understand the regional climate, structure, and stratigraphy, geomechanics, geochemistry, hydrogeology, and seismicity of the stratigraphic sequence from the surface to the water table in the vicinity of the proposed host location for the disposal borehole(s), and (3) Develop a preliminary plan and schedule, including necessary resources and costs, for a borehole disposal concept and robust and transparent pre-closure and post-closure safety assessments. The safety assessments will require iteration with process level models at both site and regional scales. Upon completion, the information collected by this effort will allow the IAEC to make decisions regarding the viability and applicability of an intermediate depth (<500m) borehole for disposal in the vadose zone of the Yamin Plain. This FY21-23 final report is provided in lieu of a workshop report that was originally planned for delivery in January, 2024. Due to the conflict in Israel and associated delays, the workshop has been delayed to April 2024. The workshop will be held at LLNL but offsite and will switch to hybrid if travel restrictions remain in place. The associated workshop report will be provided as part of a new FY24-26 LCP.

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

Initial Refinement and Optimization of the Image Reconstruction (U-MBIR) Algorithm to Optimize its Performance in Detecting Damage and Flaws

Concrete is a critical component of nuclear power plants; thus, its safety and reliability must be thoroughly examined throughout the life cycle of the structural system. During the life cycle of this infrastructure, monitoring of the concrete for signs of degradation should be performed through nondestructive evaluation (NDE). Ultrasonic measurements have been an industry standard for both surface and subsurface inspections. As such, Oak Ridge National Laboratory (ORNL) is developing advanced image reconstruction algorithms to overcome the limitations of traditional ultrasonic NDE methodologies. The results and discussion presented herein summarize the current state of the ultrasonic model–based iterative reconstruction (U-MBIR) algorithm developed at ORNL.

36 MATERIALS SCIENCE↗

Point Adversarial Self-Mining: A Simple Method for Facial Expression Recognition

In this article, we propose a simple yet effective approach, called point adversarial self mining (PASM), to improve the recognition accuracy in facial expression recognition (FER). Unlike previous works focusing on designing specific architectures or loss functions to solve this problem, PASM boosts the network capability by simulating human learning processes: providing updated learning materials and guidance from more capable teachers. Specifically, to generate new learning materials, PASM leverages a point adversarial attack method and a trained teacher network to locate the most informative position related to the target task, generating harder learning samples to refine the network. The searched position is highly adaptive since it considers both the statistical information of each sample and the teacher network capability. Other than being provided new learning materials, the student network also receives guidance from the teacher network. After the student network finishes training, the student network changes its role and acts as a teacher, generating new learning materials and providing stronger guidance to train a better student network. Here, the adaptive learning materials generation and teacher/student update can be conducted more than one time, improving the network capability iteratively. Extensive experimental results validate the efficacy of our method over the existing state of the arts for FER.

97 MATHEMATICS AND COMPUTING↗

Iterative sampling of expensive simulations for faster deep surrogate training

Deep neural network (DNN) surrogates of expensive physics simulations are enabling a rapid change in the way that common experimental design and analysis tasks are approached. Surrogate models allow simulations to be performed in parallel and separately from downstream tasks, thereby enabling analyses that would be impossible with the simulation in-the-loop; surrogates based on DNNs can effectively emulate diverse non-scalar data of the types collected in fusion and laboratory-astrophysics experiments. The challenge is in training the surrogate model, for which large ensembles of physics simulations must be run, preferably without wasting computational effort on uninteresting simulations. Here, in this paper, we present an iterative sampling scheme that can preferentially propose simulations in interesting regions of parameter space without neglecting unexplored regions, allowing high-quality and wide-ranging surrogate models to be trained using 2–3 times fewer simulations compare to space-filling designs. Our approach uses an explicit importance function defined on the simulation output space, balanced against a measure of simulation density which serves as a proxy for surrogate accuracy. It is easy to implement and can be tuned to find interesting simulations early in the study, allowing surrogates to be trained quickly and refined as new simulations become available; this represents an important step towards the routine generation of deep surrogate models quickly enough to be truly relevant to experimental work.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Technical Report on Subsurface Monitoring of the Brady Hot Spring Geothermal Site, Nevada, based upon Full Waveform Inversion

Abilities to accurately characterize the subsurface in a geothermal setting is key to assess and support production. An important element of geothermal reservoir monitoring is also the ability to investigate fluid transport within fracture network. This report focuses on improving subsurface imaging and monitoring in geothermal settings using full waveform inversion based on the adjoint method and time-lapse imaging. To assess our method, we rely on a dense seismic dataset collected in 2016 at the Brady Hot Springs geothermal site in Nevada for the DOE-funded project Poroelastic Tomography by Adjoint Inverse Modeling of Data from Seismology, Geodesy, and Hydrology. This dataset captures subsurface changes across four stages of geothermal power plant operations, which involve varying rates of fluid injection and extraction. Two velocity models were previously derived from this dataset using different methods: one based on travel times and another on sweep interferometry. Our first step is to refine these models using adjoint tomography, which has been applied successfully at global and regional-scales but is less common at the reservoir-scale. Two approaches are then explored for time-lapse analysis: directly comparing refined tomographic models from different stages or backpropagating waveform differences relative to a baseline tomographic model. The main take away is that both approaches highlight similar reservoir behaviors, but the latter approach is more computationally effective in capturing small-scale changes in subsurface properties. For this work, we leverage the use of Salvus (www.mondaic.com), an end-to-end seismic imaging solution, relying on the spectral element method to compute forward and adjoint simulations, and developed by Mondaic Ltd. It includes integrated workflow management that handles waveform and metadata, launches simulations, computes waveform misfits and adjoint sources, and iterates for model updates by nonlinear optimization.

15 GEOTHERMAL ENERGY↗

Solution Irregularity Remediation for Spatial Discretization Error Estimation for S N Transport Solutions

The discrete ordinates linear Boltzmann transport equation is typically solved in its spatially discretized form, incurring spatial discretization error. Quantification of this error for purposes such as adaptive mesh refinement or error analysis requires an a posteriori estimator, which utilizes the numerical solution to the spatially discretized equation to compute an estimate. Because the quality of the numerical solution informs the error estimate, irregularities, present in the true solution for any realistic problem configuration, tend to cause the largest deviation in the error estimate vis-a-vis the true error. In this paper, an analytical partial singular characteristic tracking (pSCT) procedure for reducing the estimator’s error is implemented within our novel residual source estimator for a zeroth-order discontinuous Galerkin scheme, at the additional cost of a single inner iteration. Here, a metric-based evaluation of the pSCT scheme versus the standard residual source estimator is performed over the parameter range of a Method of Manufactured Solutions test suite. The pSCT scheme generates near-ideal accuracy in the estimate in problems where the dominant source of the estimator’s error is the solution irregularity, namely, problems where the true solution is discontinuous and problems where the true solution’s first derivative is discontinuous and the scattering ratio is low. In problems where the scattering ratio is high and the true solution is discontinuous in the first derivative, the error in the scattering source, which is not converged by the pSCT scheme, is greater than the error incurred due to the irregularity. Ultimately, a pSCT scheme is judged to be useful for error estimation in problems where the computational cost of the scheme is justified. In the presence of many irregularities, such a scheme may be intractable for general use, but in benchmarks, as an analytical tool, or in problems that have nondissipative discontinuities, the scheme may prove invaluable.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm

Consider a scalar field f : M → R, where M is a triangulated simplicial mesh in R d . A level set, or contour, at value v is a connected component of f –1 (v). As v is changed, these contours change topology, merge into each other, or split. Contour trees are concise representations of f that track this contour behavior. The vertices of these trees are the critical points of f, where the gradient is zero. The edges represent changes in the topology of contours. It is a fundamental data structure in data analysis and visualization, and there is significant previous work (both theoretical and practical) on algorithms for constructing contour trees. Suppose M has n vertices, N facets, and t critical points. A classic result of Carr, Snoeyink, and Axen (2000) gives an algorithm that takes O(n log n+Nα(N)) time (where α(·) is the inverse Ackermann function). A further improvement to O(t log t + N) time was given by Chiang et al. All these algorithms involve a global sort of the critical points, a significant computational bottleneck. Unfortunately, lower bounds of Ω(t log t) also exist. We present the first algorithm that can avoid the global sort and has a refined time complexity that depends on the contour tree structure. Intuitively, if the tree is short and fat, we get significant improvements in running time. For a partition of the contour tree into a set of descending paths, P, our algorithm runs in O($\Sigma$ pϵP |p| log |p| + tα(t) + N). This is at most O(t log D + N), where D is the diameter of the contour tree. Moreover, it is O(tα(t) + N) for balanced trees, a significant improvement over the previous complexity. Our algorithm requires numerous ideas: partitioning the contour tree into join and split trees, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. There is a crucial use of a family of binomial heaps to maintain priorities, ensuring that any comparison made is between comparable nodes of the contour tree. We also prove lower bounds showing that the $\Sigma$ pϵP |p| log |p| complexity is inherent to computing contour trees.

97 MATHEMATICS AND COMPUTING↗