Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “triangulation”

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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
DOE OSTI2025

Sharp front tracking with geometric interface reconstruction

Here, this paper presents a novel sharp front-tracking method designed to address limitations in classical front-tracking approaches, specifically their reliance on smooth interpolation kernels and extended stencils for coupling the front and fluid mesh. In contrast, the proposed method employs exclusively sharp, localized interpolation and spreading kernels, restricting the coupling to the interfacial fluid cells–those containing the interface/front. This localized coupling is achieved by integrating a divergence-preserving velocity interpolation method with a piecewise parabolic interface calculation (PPIC) and a polyhedron intersection algorithm to compute the indicator function and local interface curvature. Surface tension is computed using the Continuum Surface Force (CSF) method, maintaining consistency with the sharp representation. Additionally, we propose an efficient local roughness smoothing implementation to account for surface mesh undulations, which is easily applicable to any triangulated surface mesh. Building on our previous work, the primary innovation of this study lies in the localization of the coupling for both the indicator function and surface tension calculations. By reducing the interface thickness on the fluid mesh to a single cell, as opposed to the 4–5 cell spans typical in classical methods, the proposed sharp front-tracking method achieves a highly localized and accurate representation of the interface. This sharper representation mitigates parasitic currents and improves force balancing, making it particularly suitable for scenarios where the interface plays a critical role, such as microfluidics, fluid-fluid interactions, and fluid-structure interactions. The proposed method is comprehensively validated and tested on canonical interfacial flow problems, including stationary and translating Laplace equilibria, oscillating droplets, and rising bubbles. The presented results demonstrate that the sharp front-tracking method significantly outperforms the classical approach in terms of accuracy, stability, and computational efficiency. Notably, parasitic currents are reduced by approximately two orders of magnitude and stable results are obtained for parameter ranges where classical front tracking fails to converge.

42 ENGINEERING↗
DOE OSTI2023

Machine-to-machine variability of roughness and corrosion in additively manufactured 316L stainless steel

Numerous studies on the corrosion response of metal AM have been conducted. Nonetheless, the specimens being tested are commonly ground or polished to remove the outer as-built surface. If metal AM is truly going to be employed as a transformative technology that can produce complex shapes that do not require traditional machining, then the material needs to be evaluated in the as-built state. The reality is that AM alloys have shown significant inconsistencies regarding as-built surface texture, topology, and residual stress. One metric that has shown significant unpredictability in the literature is the susceptibility to localized corrosion of typically passive alloys, such as stainless steel (SS). There are a large number of studies that have attempted to understand the corrosion response of metal AM materials, but these studies are typically performed on materials that have been printed on a single machine and often mechanically polished to a smooth finish. This study compares the corrosion response of as-built AM, laser-beam powder bed fusion (LB-PBF), 316L SS parts that have been fabricated on five different machines. The majority of this work focused on understanding the susceptibility to localized corrosion of AM metals with respect to machine-dependent variables, namely surface roughness, and build angle. Surface roughness data was collected using scanning white light triangulation, laser scanning confocal microscopy, and coherence scanning interferometry. The results show that there is significant variability (p two-tail < 0.05) in the susceptibility to local corrosion initiation of LB-PBF 316L SS samples built on different machines. Surface oxides were probed with electron dispersive spectroscopy and revealed that variations in local corrosion susceptibility likely arise from differences in the stability of the passive film caused by chemical segregation, unique microstructure, and tortuous roughness features at the as-built surfaces. The variability of roughness and corrosion properties from test samples printed on different machines was corroborated by property measurements performed at five different testing sites, proving reproducibility of the data. Most importantly, this study shows that if the as-built surface layer is removed through grinding or electropolishing the machine-to-machine variation observed in the corrosion susceptibility is reduced.

36 MATERIALS SCIENCE↗
DOE OSTI2022

Vision-based inspection of prefabricated components using camera poses: Addressing inherent limitations of image-based 3D reconstruction

Modular construction can lead to additional cost overruns and delays when a defect is found on the construction site and is not easily repairable. Researchers have developed various methods that use image-based 3D reconstruction for quality assessment, but they have inherent limitations, such as inconsistency and dealing with surfaces with reflectivity and limited visual features. Therefore, this paper presents a vision-based quality assessment method using cameras for prefabricated components by addressing these limitations. Specifically, this paper proposes a novel quality inspection method with sub-millimeter accuracy using cameras focused on leveraging camera poses (as opposed to 3D point clouds that are often not consistent in quality) from the image-based 3D reconstruction. The 3D point estimation by computing triangulation was used for achieving accurate measurement. The proposed method is validated using six different variances and two case studies – an aluminum pipe with a reflective surface and a fabricated concrete column. Furthermore, the results demonstrate the accuracy and effectiveness of the proposed method.

42 ENGINEERING↗
DOE OSTI2023

Three‐Dimensional Broadband Interferometric Mapping and Polarization (BIMAP‐3D) Observations of Lightning Discharge Processes

Abstract Following on our earlier single‐station, 2‐dimensional (2D) broadband interferometric mapping and polarization (BIMAP) observations of lightning discharges, we recently deployed two BIMAP stations at Los Alamos National Laboratory to map the lightning sources and their polarization in full 3‐dimensional (3D) space (BIMAP‐3D). The two stations are separated by 11.5‐km and each station consists of four antenna sets (instead of three for the original BIMAP) that form a Y ‐shaped array for improved interferometric performance. In this paper, we report the BIMAP‐3D system design, a generalized and analytical 2D interferometry technique for noncoplanar antenna array, a two‐stage 3D mapping technique based on geometric triangulation and baseline‐based differential time of arrival, and a technique to reconstruct the polarization orientation in 3D space by combining the 2D polarization results from the two‐station observations. Along with description of the techniques, we demonstrate and discuss the initial lightning results, including 3D maps for a hybrid intracloud and cloud‐to‐ground flash and for a normal intracloud flash, development of abnormal K‐change leaders, and polarization signatures for a K‐change leader. We find that with the two‐stage 3D mapping techniques, the sources can be located to meters accuracy for a favorable event that occurs between the two stations. We also find the polarization vectors for the example K leader are mostly orthogonal to the leader channel after the full 3D polarization analysis. The main purpose of this paper is to report the BIMAP‐3D techniques and capabilities. Detailed analysis of more specific discharge processes will be reported in later studies.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2025

BCFW tilings and cluster adjacency for the amplituhedron

In 2005, Britto, Cachazo, Feng, and Witten gave a recurrence (now known as the BCFW recurrence) for computing scattering amplitudes in N = 4 super Yang–Mills theory. Arkani-Hamed and Trnka subsequently introduced the amplituhedron to give a geometric interpretation of the BCFW recurrence. Arkani-Hamed and Trnka conjectured that each way of iterating the BCFW recurrence gives a “triangulation” or “tiling” of the m=4 amplituhedron. In this article, we prove the BCFW tiling conjecture of Arkani-Hamed and Trnka. We also prove the cluster adjacency conjecture for BCFW tiles of the amplituhedron, which says that facets of tiles are cut out by collections of compatible cluster variables for the Grassmannian Gr4,n. Moreover we show that each BCFW tile is the subset of the Grassmannian where certain cluster variables have particular signs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

MOOSE Reactor Module: An Open-Source Capability for Meshing Nuclear Reactor Geometries

The U.S. Department of Energy (DOE) Nuclear Energy Advanced Modeling and Simulation (NEAMS) program has developed numerous physics solvers utilizing the open-source Multiphysics Object-Oriented Simulation Environment (MOOSE) framework for multiphysics reactor analysis. These solvers require input finite element meshes representing the discretized spatial domain. Typically, reactor analysts turn to licensed tools for the creation of reactor geometry meshes. Recently, open-source functionality has been added to the MOOSE framework to mesh common reactor geometries and improve MOOSE-based nuclear reactor application user workflows. The new functionality is primarily contained in the new Reactor module of MOOSE and includes support for hexagonal pins, assemblies, and cores, extended Cartesian geometry support, options for modeling static and rotating control drums within a hexagonal assembly, core periphery triangulation, and automatic tagging of pin, assembly, plane, and depletion regions for easier post processing of physics results. A set of reactor geometry mesh builder objects further streamlines the construction of hexagonal and Cartesian cores and allows mapping of materials to regions during mesh generation. The meshes produced with the MOOSE Reactor module may be used directly within MOOSE-based applications or exported as Exodus II files for use in other finite element solvers. The tools have been demonstrated and verified using a variety of NEAMS physics solvers on a range of reactor applications, including a sodium-cooled fast reactor core analysis using Griffin, a fast reactor assembly thermal deformation analysis using MOOSE Tensor Mechanics, and a heat pipe–cooled microreactor coupled analysis using Griffin, Bison, and Sockeye. MOOSE’s Reactor module provides significant advantages compared to the use of external meshing tools when analyzing Cartesian and hexagonal reactor lattices using MOOSE-based applications: immediate accessibility (open-source) to the end user, low barrier to entry for new users, speed of mesh generation, volume preservation of meshed fuel pins, and simplification of analysis workflow when used in conjunction with MOOSE-based applications.

99 GENERAL AND MISCELLANEOUS↗
DOE OSTI2023

Graph Neural Network for Object Reconstruction in Liquid Argon Time Projection Chambers

The Exa.TrkX project presents a graph neural network (GNN) technique for low-level reconstruction of neutrino interactions in a Liquid Argon Time Projection Chamber (LArTPC). GNNs are still a relatively novel technique, and have shown great promise for similar reconstruction tasks in the Large Hadron Collider (LHC). Graphs describing particle interactions are formed by treating each detector hit as a node, with edges describing the relationships between hits. We utilise a multi-head attention message passing network which performs graph convolutions in order to label each node with a particle type.We present an updated variant of our GNN architecture, with several improvements. After testing the model on more realistic simulation with regions of unresponsive wires, the target was modified from edge classification to node classification in order to increase robustness. Removing edges as a classification target opens up a broader possibility space for edge-forming techniques; we explore the model’s performance across a variety of approaches, such as Delaunay triangulation, kNN, and radius-based methods. We also extend this model to the 3D context, sharing information between detector views. By using reconstructed 3D spacepoints to map detector hits from each wire plane, the model naively constructs 2D representations that are independent yet fully consistent.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2025

Dark matter substructure or source model systematics? A case study of cluster lens Abell S1063

Mapping the small-scale structure of the universe through gravitational lensing is a promising tool for probing the particle nature of dark matter. Curved Arc Basis (CAB) has been proposed as a local lensing formalism in galaxy clusters, with the potential to detect low-mass dark matter substructure. In this work, we analyse the cluster lens Abell S1063 in search of dark matter substructure with the CAB formalism, using multiband imaging data from James Webb Space Telescope ( JWST ). We use two different source modelling methods: shapelets and pixel-based source reconstruction based on Delaunay triangulation. We find that source modelling systematics from shapelets result in a disagreement between CAB parameters measured from different filters. Source modelling with Delaunay significantly alleviates this systematic, as seen in the improvement in agreement across filters. We also find that inadequate complexity in source modelling can result in convincing spurious detections of dark matter substructure from strong gravitational lenses, as seen by our $\Delta \text{BIC} > 20$ measurement of a $M \sim 10^{10}$ ${\rm M}_{\odot }$ subhalo with shapelets, a spurious detection that is not reproduced with Delaunay source modelling. We demonstrate that multiband analysis with different JWST filters is key for disentangling source and lens model systematics from dark matter substructure detections.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2025

Dynamical dark energy from lattice quantum gravity

We study the behavior of the vacuum in Euclidean dynamical triangulations (EDT). Algorithmic improvements and better lattice spacing determinations allow us to test the properties of the emergent de Sitter geometries of our simulations to higher precision than previously possible. Although the agreement with de Sitter is good, the improved precision reveals deviations that can be interpreted as nontrivial vacuum dynamics, well described by a cosmological constant that runs with scale. The simulations show that the dominant running is quadratic and that the scale can be identified with the Hubble rate. Several key cross-checks support this picture, including consistent results across multiple lattice spacings and the fact that the null energy condition is not violated. The parameters of the running are fully determined by simulations, enabling predictions when extrapolated to the scales relevant for our Universe. This leads to a model for dark energy that is compatible with current observations, but which predicts deviations from the Standard Model of cosmology at the 𝒪⁡(10 −3 ) level in observables that could be tested with future improvements in precision measurements.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2026

Supersymmetric lattice theories on curved space

We show how to construct Hamiltonian lattice theories with one exact supersymmetry on arbitrary triangulations of curved space in any number of dimensions. Both bosons and fermions satisfy discrete Kähler-Dirac equations. The quantization of the fermions proceeds by imposing conventional anticommutation relations while the bosons require a modification of the usual canonical commutator. On regular lattices we construct parity, time reversal and translation-by-one (shift) symmetries. We argue that the latter are generically noninvertible symmetries. We also show how to couple these degrees of freedom to background gauge fields which leads to a theory with enhanced supersymmetry.

Anomalies↗
DOE OSTI2023

Visualizing Fault Induced Traveling Waves In Medium Voltage Systems

Traveling waves are induced in power systems during most transient events in the grid. These waves travel close to the speed of light in overhead lines and 50% to 60% the speed of light in underground cables. Even though traveling wave-based protection schemes for transmission systems are available commercially, traveling waves in medium voltage distribution networks are still in research space. Compared to transmission system, medium voltage distribution systems contain more reflections and refractions. Thus, visualization is challenging and is critical in locating faults in distribution network. To address this visualization challenge, this paper presents an open-source tool to visualize the traveling waves using Bewley lattice approach. The developed visualization tool will be useful for the protection engineers to detect and triangulate fault locations in the medium voltage systems and isolate the faults.

Bewley Lattice↗
DOE OSTI2024

Localized Evaluation for Constructing Discrete Vector Fields

Topological abstractions offer a method to summarize the behavior of vector fields, but computing them robustly can be challenging due to numerical precision issues. One alternative is to represent the vector field using a discrete approach, which constructs a collection of pairs of simplices in the input mesh that satisfies criteria introduced by Forman's discrete Morse theory. While numerous approaches exist to compute pairs in the restricted case of the gradient of a scalar field, state-of-the-art algorithms for the general case of vector fields require expensive optimization procedures. This paper introduces a fast, novel approach for pairing simplices of two-dimensional, triangulated vector fields that do not vary in time. The key insight of our approach is that we can employ a local evaluation, inspired by the approach used to construct a discrete gradient field, where every simplex in a mesh is considered by no more than one of its vertices. Specifically, we observe that for any edge in the input mesh, we can uniquely assign an outward direction of flow. We can further expand this consistent notion of outward flow at each vertex, which corresponds to the concept of a downhill flow in the case of scalar fields. Working with outward flow enables a linear-time algorithm that processes the (outward) neighborhoods of each vertex one-by-one, similar to the approach used for scalar fields. Here, we couple our approach to constructing discrete vector fields with a method to extract, simplify, and visualize topological features. Empirical results on analytic and simulation data demonstrate drastic improvements in running time, produce features similar to the current state-of-the-art, and show the application of simplification to large, complex flows.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

BDEM (Discrete-element-simulator for high-solids granular flows) [SWR-22-72]

BDEM is a discrete element method based simulation tool developed specifically for modeling high-solids granular flows that include polydispersity, heat-transfer, moving boundaries and chemistry. Our solver provides facilities for simulating spherical/non-spherical particles with modified contact and friction models in complex dynamic geometries defined using level-sets or triangulated files. The solver is developed on top of NREL's open-source performance portable library, AMReX, providing parallel execution capabilities on current and upcoming high-performance-computing (HPC) architectures. Simulations at the scale of several millions to billion particles have been performed using this software on large scale computing resources. This software can be applied to non-reacting solids dominant flows in silos, hoppers and screw conveyors as well as in high temperature reacting systems such as screw kilns and auger reactors.

Sitaraman, Hariswaran↗
DOE OSTI2021

Model, data, and code for paper "Modeling of streamflow in a 30-kilometer-long reach spanning 5 years using OpenFOAM 5.x"

The data package includes data, model, and code that support the analyses and conclusions in the paper titled “modeling of streamflow in a 30-kilometer-long reach spanning 5 years using OpenFOAM 5.x”. The primary goal of this paper is to demonstrate that key streamflow properties such as water depth, flow velocity, and dynamic pressure in a natural river at 30-kilometer scale over 5 years can be reliably and efficiently modeled using the computational framework presented in this paper. To support the paper, various data types from remote sensing, field observations, and computational models are used. Specific details are described as follows. Firstly, the river bathymetry data was obtained from a Light Detection and Ranging (LiDAR) survey. This data is then converted to a triangulated surface format, STL, for mesh generation in OpenFOAM. The STL data can be found in Model_Setups/BaseCase_2013To2015/constant/triSurface. The OpenFOAM mesh generated using this STL file can be found in constant/polyMesh. Other model setups, boundary and initial conditions can be found in /system and /0.org under folder BaseCase_2013To2015. A similar data structure can also be found in BaseCase_2018To2019 for the simulations during 2018 and 2019. Secondly, the OpenFOAM simulations need the upstream discharge and water depth information at the upstream boundary to drive the model. These data are generated from a one-dimensional hydraulic model and the data can be found under the folder Model_Setups /1D model Mass1 data. The mass1_65.csv and mass1_191.csv files include the results of the 1D model at the model inlet and outlet, respectively. The Matlab source code Mass1ToOFBC20182019.m is used to convert these data into OpenFOAM boundary condition setups.With the above OpenFOAM model, it can generate data for water surface elevation, flow velocity, and dynamic pressure. In this paper, the water surface elevation was measured at 7 locations during different periods between 2011 and 2019. The exact survey locations (see Fig1_SurveyLocations.txt) can be found in folder Fig_1. The variation of water stage over time at the 7 locations can be found in folder /Observation_WSE. The data type include .txt, .csv, .xlsx, and .mat. The .mat data can be loaded by Matlab.We also measured the flow velocities at 12 cross-sections along the river. At each cross-section, we recorded the x, y locations, depth, three velocity components u,v,w. These data are saved to a Matlab format which can be found under folder /Observation_Velocity and /Fig_1. The relative locations of velocity survey locations to the river bathymetry can be found in Figure 1c.The water stage data at the 7 locations from OpenFOAM, 1D, and 2D hydraulic models are also provided to evaluate the long-term performance of 3D models vs 1D/2D models. The water stage data for the 7 locations from OpenFOAM have been saved to .mat format and can be found in /OpenFOAM_WSE. The water stage data from the 1D model are saved in .csv format and can be found in /Mass1_WSE. The water stage from the 2D model is saved as .mat format and can be found in / Mass2_WSEIn addition, the OpenFOAM model outputs the information of hydrostatic and hydrodynamic pressure. They are saved as .mat format under folder /Fig_11/2013_1. As the files are too large, we only uploaded the data for January 2013. The area of different ratio of dynamic pressure to static pressure for all simulation range, i.e., 2013-2015, are saved to .mat format. They can be found in /Fig_11/PA. Further, the data of wall clock time versus the solution time of the OpenFOAM modeling are also saved to .mat format under folder /Fig_13/LogsMat. In summary, the data package contains seven data types, including .txt, .csv, .xlsx, .dat, .stl, .m, and .mat. The former 4 types can be directly open using a text editor or Microsoft Office. The .mat format needs to be read by Matlab. The Matlab source code .m files need to be run with Matlab. The OpenFOAM setups can be visualized in ParaView. The .stl file can be opened in ParaView or Blender. The data in subfolders Fig_1 to Fig_10 and Fig_12 are copied from the aforementioned data folders to generate specific figures for the paper. A readME.txt file is included in each subfolder to further describe how the data in each folder are generated and used to support the paper.Please use the data package's DOI to cite the data package. Please contact yunxiang.chen@pnnl.gov if you need more data related to the paper.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2026

Stereo Cameras for Clouds (STEREOCAM) Instrument Handbook

The three pairs of stereo camera setups aim to provide synchronized and stereo calibrated time series of images that can be used for 3D cloud mask reconstruction. Each camera pair is positioned at approximately 120 degrees from the other pair, with a 17o-19o pitch angle from the ground, and at 5-6 km distance from the U.S. Department of Energy (DOE) Central Facility at the Atmospheric Radiation Measurement (ARM) Climate Research Facility Southern Great Plains (SGP) observatory to cover the region from northeast, northwest, and southern views. Images from both cameras of the same stereo setup can be paired together to obtain 3D reconstruction by triangulation. 3D reconstructions from the ring of three stereo pairs can be combined together to generate a 3D mask from surrounding views. This handbook delivers all stereo reconstruction parameters of the cameras necessary to make 3D reconstructions from the stereo camera images.

47 OTHER INSTRUMENTATION↗
DOE OSTI2023

Retrieving Point Cloud of Cloud Points (PCCP) Value-Added Product from Stereo Cameras

In this report, we refer to a pair of cameras that capture synchronized pictures with overlapping fields of view (FOV) as a stereo pair. Each stereo pair independently performs a stereo reconstruction of cloud points. Currently, there are three U.S. Department of Energy Atmospheric Radiation Measurement (ARM) user facility stereo pairs (six cameras in total) positioned around the Southern Great Plains (SGP) observatory’s Central Facility (CF; Romps and Oktem 2017). Time-synchronized pictures from the two cameras in a stereo pair can be paired together to obtain a three-dimensional (3D) reconstruction of feature points by triangulation. This document explains how we use ARM stereo cameras and stereophotogrammetric principles to generate the Point Cloud of Cloud Points (PCCP) Value-Added Product (VAP). The PCCP VAP is essentially a set of 3D positions representing the locations of cloud features in the sky. Thousands of cloud features can be reconstructed instantly in each stereo pair's FOV, which covers an area of tens of square kilometers. Cloud base and cloud top heights can be extracted from the PCCP product.

42 ENGINEERING↗
DOE OSTI2021

Frequency Comb-Based Remote Methane Observation Network (Final Scientific/Technical Report)

ARPA-E investment in long-range, frequency comb-based methane detection has resulted in the first scalable, cost-effective continuous methane emissions system. At the onset of this ARPA-E MONITOR award, the dual-frequency comb spectrometer was a sprawling, expensive, laboratory-confined device which had only recently been demonstrated capable of measuring atmospheric trace gases over open-paths. Bringing the technology to the point of being able to monitor for and characterize methane emissions at oil and natural gas production facilities seemed an almost impossible task. Over the subsequent months and years, our team transitioned the Nobel-prize-winning frequency-comb-laser spectrometer technology to a field-deployed regional methane leak detection system. The spectrometer enables highly sensitive near-infrared absorption measurements of methane along kilometer-scale laser beam paths. The measurements are coupled with an atmospheric modeling and inversion framework to triangulate the location of emission sources and quantify the emission rates.

03 NATURAL GAS↗
DOE OSTI2022

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↗