text: This paper presents a new algorithm for the fast, shared memory, multi-core computation of augmented contour trees on triangulations. In contrast to most existing parallel algorithms our technique computes augmented trees, enabling the full extent of contour tree based applications including data segmentation. Our approach completely revisits the traditional, sequential contour tree algorithm to re-formulate all the steps of the computation as a set of independent local tasks. This includes a new computation procedure based on Fibonacci heaps for the join and split trees, two intermediate data structures used to compute the contour tree, whose constructions are efficiently carried out concurrently thanks to the dynamic scheduling of task parallelism. We also introduce a new parallel algorithm for the combination of these two trees into the output global contour tree. Overall, this results in superior time performance in practice, both in sequential and in parallel thanks to the OpenMP task runtime. We report performance numbers that compare our approach to reference sequential and multi-threaded implementations for the computation of augmented merge and contour trees. These experiments demonstrate the run-time efficiency of our approach and its scalability on common workstations. We demonstrate the utility of our approach in data segmentation applications.
  @cite_41: This paper summarizes results of a study of the design and application of special-purpose computers for the simulation of air-to-ground radars. Specifically, the computers must generate information in real-time to simulate the display of a scanning radar in a vehicle flying at Mach 3 and arbitrary altitude. The radar can view 105 square miles of terrain per second with a resolution of 60 points per mile in range (five per microsecond). This paper describes a hybrid simulator that exploits both the redundancy in the terrain and the repetitiveness caused by the radar scan pattern. An overall design is presented that affords reductions of 103 in storage capacity and computation speed, compared with a straightforward digital approach for generation of topographic profiles from which the display is prepared. Details are presented of data formats and transfer schemes through the memory hierarchy, and of algorithms for the reconstruction of analog profiles from a digitally stored contour map.
  @cite_62: We show that contour trees can be computed in all dimensions by a simple algorithm that merges two trees. Our algorithm extends, simplifies, and improves work of Tarasov and Vyalyi and of van
  @cite_52: 
summary: The contour tree @cite_41 , a tree that contracts connected components of to points (formally defined in section:Background ), is closely related to the notion of merge tree, which contracts connected components of to points on simply connected domains. As shown by Tarasov and Vyali @cite_52 and later generalized by @cite_62 in arbitrary dimension, the contour tree can be efficiently computed by combining with a simple linear-time traversal the merge trees of the input function and of its opposite (called the join and split trees, see section:Background ). Due to this tight relation, merge and contour trees have often been investigated jointly in the literature.