Mathematics and Visualization Hamish Carr · Issei Fujishiro · Filip Sadlo Shigeo Takahashi Editors Topological Methods in Data Analysis and Visualization V Theory, Algorithms, and Applications Mathematics and Visualization SeriesEditors Hans-ChristianHege,Konrad-Zuse-ZentrumfürInformationstechnikBerlin(ZIB), Berlin,Germany David Hoffman, Department of Mathematics, Stanford University, Stanford, CA, USA ChristopherR.Johnson,ScientificComputingandImagingInstitute,SaltLake City,UT,USA KonradPolthier,AGMathematicalGeometryProcessing,FreieUniversitätBerlin, Berlin,Germany The series Mathematics and Visualization is intended to further the fruitful relationship between mathematics and visualization. It covers applications of visualization techniques in mathematics, as well as mathematical theory and methodsthatareusedforvisualization.Inparticular,itemphasizesvisualizationin geometry, topology, and dynamical systems; geometric algorithms; visualization algorithms; visualization environments; computer aided geometric design; computationalgeometry;imageprocessing;informationvisualization;andscientific visualization.Threetypesofbookswillappearintheseries:researchmonographs, graduatetextbooks,andconferenceproceedings. Moreinformationaboutthisseriesathttp://www.springer.com/series/4562 Hamish Carr (cid:129) Issei Fujishiro (cid:129) Filip Sadlo (cid:129) Shigeo Takahashi Editors Topological Methods in Data Analysis and Visualization V Theory, Algorithms, and Applications Editors HamishCarr IsseiFujishiro UniversityofLeeds KeioUniversity Leeds,UK Yokohama,Kanagawa,Japan FilipSadlo ShigeoTakahashi HeidelbergUniversity,IWR UniversityofAizu Heidelberg,Germany Aizu-WakamatsuCity,Fukushima,Japan ISSN1612-3786 ISSN2197-666X (electronic) MathematicsandVisualization ISBN978-3-030-43035-1 ISBN978-3-030-43036-8 (eBook) https://doi.org/10.1007/978-3-030-43036-8 MathematicsSubjectClassification:76M24,53A45,62-07,62H35,65D18,65U05,68U10 ©SpringerNatureSwitzerlandAG2020 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthors,andtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressedorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictional claimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG. Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface Thirty years ago, the field of scientific visualization established the importance of studying systematic methods for representing data on screen, in particular for functionscomputedoverEuclideanspace.Astime haspassed,thedata sizeshave increased to the point where it is no longer feasible to present all of the data to a human interpreter, and scientific visualization has therefore depended ever more heavily on analytic techniques to extract significant information for human consideration. One of the most successful approacheshas been the application of topological analysis to data, and the past 30years have seen a consistent expansionin theory, technique, algorithm, and application. Initially confined to vector field topology, thecommunitydevelopedideasinscalarfieldtopology,persistenthomology,tensor fieldtopology,multivariatetopology,aswellasspecializedapproachesforparticular datasources. Oneofthehallmarksofthisworkhasbeentheapplicationoftopologicalanalysis toscientificproblemsatscaleandafocusoncomputationallytractableapproaches. As a result, the TopoInVis community was developed to support visualization expertsintheirtopologicalwork. Starting in 2005, biennial workshops have been held on topological visual- ization in Budmerice (2005), Grimma (2007), Snowbird (2009), Zürich (2011), Davis (2013), Annweiler (2015), and Tokyo (2017), where informal discussions supplement formal presentations and knit the community together. Notably, these workshops have consistently resulted in quality publications under the Springer imprintwhichformasignificantpartoftheworkingknowledgeinthearea. At the 2017 workshop at Keio University in Tokyo, scalar topology was the largestareaofinterest,incontrasttopreviousyearswhenvectortopologyhasoften beenthedominantarea.Vectortopologycontinuestobevisible,asdoestherecent growth in multivariate topology. At the same time, tensor topology is an area of continuingwork,andadditionaltypesoftopologyalsoshowupfromtimetotime, whileapplicationscontinuedtobe ofinteresttoallpresent,andthekeynotesboth addressedapplicationproblems. v vi Preface Ofthe23paperspresentedatTopoInVis2017,16passedasecond-roundreview processforthisvolume.Ingroupingthesepapers,thelargestnumber(7)relatedto scalarfieldtopologyandhavebeendividedintothreepapersonpersistenthomology that are more theoretical plus a further four that are more applied, including one paperdealingwithpathologicalandtestcasesthatstraddlesscalarandmultivariate problems. Inthefirstgroup,thefirstpaperinvestigatesnewmethodsofdefininghierarchies frompersistencepairings,toprovideabetterrepresentationofcomplexscalardata sets.Thesecondpaper,whichreceivedthebestpaperawardattheworkshop,gives an innovative new approach for computing merge trees in a form amenable to shared-memory parallel implementation. The third paper tackles the problem of extending existing forms of persistent topology to data sets sampled from non- manifold inputs. In all of these papers, the common concern is to extend the theoreticalframeworkswhichsupportthetopologicalinvestigationofdata. The second group of papers is more oriented to practical details than to the underlying theory. In the first paper, topological tools are extended to help understandsearchspacesfromoptimizationproblemsbydefiningacollapsedmeta landscape that represents the original space at a coarse-grainedlevel. The second paper explores automated methods for choosing transfer functions that highlight topologicalfeatureseffectivelyindirectvolumerendering(DVR).Thethirdpaper also relates to a practical problem: that persistence diagrams are expensive to compare,substitutingapersistenceindicatorfunction(PIF)thatismoreamenable to data analysis. Finally, this group includes a paper on a part of topological computation that is rarely addressed in papers due to space limitations: effective methodsand test sets for debuggingtopologicalcode, including papermodels for smallpracticalReebspacesforinstructionalpurposes. In the third group of papers, the authors consider the question of topological variationovertime.Here,thefirstpaperlooksattheuseofmergertreestovisualize dark matter halos in cosmological simulations. The second tackles a different problem,theanalysisoffingersinasimulationofviscousfluidbyusingpersistent tracking over time to identify how fingers merge, grow, and separate. Finally, the third paper tackles the problem of tracking distinct topologicalregionsover time, and how local decision-making generates broken tracks, while global decision- makingprovidesimprovedtrackingoffeatures. All three of these groups deal primarily with the simplest case for topological analysis: that of scalar field analysis and its variants. The fourth group of papers tacklesoneoftherecentdevelopmentsinthearea:theuseoftopologicalanalysisfor bivariateandmultivariatedata. Thefirst of these papersconsiderstheuse ofJoint Contour Nets, a discrete topologicalstructure, to approximate the Pareto analysis of data. In the secondpaper,existingwork on scalar topologicaluser interfacesis extended to bivariate data through the use of fiber surfaces, while the final paper considerscombinationsoftopologicaldatastructures,suchasthecontourtreeand Morse–Smalecomplex. Thisleavesonelastgroup,whichdealswithallotherformsoftopology.Whereas previousyearshaveoftenseena predominanceofvectorfield analysis,thisyear’s Preface vii workshopacceptedonepaperonvectors,asecondontensors,andathirdonsurface topology. In the first of these, Galilean invariance is applied to provide vector analysis that is independentof the frame of referenceof the analysis. The second paper extends previous work on tensor field analysis by proving a maximum on thenumberofcriticalpointspossibleinalinearlyinterpolatedtensorfield.Finally, the last paperlooksat new formsof shape analysis of surfacesbased on Poincaré duality. Lookingbackatthiscollectionofpapers,wecanseethat,althoughthespecific areas of interest ebb and flow, the concern for theory, practical techniques, and applicationscontinues,andthatasnewformsoftopologicalanalysisareintroduced, theystimulateagreatdealofdetailwork.However,onceestablished,areascontinue duetotheirongoingapplicabilitytopracticalvisualdataanalysis,showingthevalue toourcommunityofthisongoingSpringerbookseries. We would therefore like to thank all of the participants of TopoInVis 2017, as well as Springer for their continued support, and anticipate future workshops will continue the process. We would also like to thank Tateishi Science and TechnologyFoundationandtheTelecommunicationsAdvancementFoundationfor theirgenerousfinancialsupportoftheworkshop. Leeds,UK HamishCarr Yokohama,Japan IsseiFujishiro Heidelberg,Germany FilipSadlo Aizu-Wakamatsu,Japan ShigeoTakahashi Co-Chairs,TopoInVis2017 Contents PartI Persistence HierarchiesandRanksforPersistencePairs ................................. 3 BastianRieck,FilipSadlo,andHeikeLeitte TripletMergeTrees.............................................................. 19 DmitriySmirnovandDmitriyMorozov PersistentIntersectionHomologyfortheAnalysisofDiscreteData ....... 37 BastianRieck,MarkusBanagl,FilipSadlo,andHeikeLeitte PartII ScalarTopology Coarse-GrainingLargeSearchLandscapesUsingMassiveEdge Collapse ........................................................................... 55 SebastianVolke,MartinMiddendorf,andGerikScheuermann AdjustingControlParametersofTopology-AccentuatedTransfer FunctionsforVolumeRaycasting .............................................. 71 YurikoTakeshima,ShigeoTakahashi,andIsseiFujishiro TopologicalMachineLearningwithPersistenceIndicatorFunctions ..... 87 BastianRieck,FilipSadlo,andHeikeLeitte PathologicalandTestCasesforReebAnalysis ............................... 103 HamishCarr,JulienTierny,andGuntherH.Weber PartIII Time-VaryingTopology AbstractedVisualizationofHaloTopologiesinDarkMatter Simulations ....................................................................... 123 KarstenSchatz,JensSchneider,ChristophMüller,MichaelKrone, GuidoReina,andThomasErtl ix x Contents PersistenceConceptsfor2DSkeletonEvolutionAnalysis................... 139 BastianRieck,FilipSadlo,andHeikeLeitte FastTopology-BasedFeatureTrackingusingaDirectedAcyclic Graph.............................................................................. 155 HimangshuSaikiaandTinoWeinkauf PartIV MultivariateTopology TheApproximationofParetoSetsUsingDirectedJointContourNets.... 173 JanBormann,LarsHuettenberger,andChristophGarth FlexibleFiberSurfaces:AReeb-FreeApproach............................. 187 DaisukeSakurai,KenjiOno,HamishCarr,JorjiNonaka,andTomohiro Kawanabe TopologicalSubdivisionGraphsforComparativeandMultifield Visualization...................................................................... 203 ChristianHeineandChristophGarth PartV OtherFormsofTopology InterpretingGalileanInvariantVectorFieldAnalysisviaExtended Robustness ........................................................................ 221 BeiWang,RoxanaBujack,PaulRosen,PrimozSkraba,HarshBhatia,and HansHagen MaximumNumberofTransitionPointsin3DLinearSymmetric TensorFields...................................................................... 237 YueZhang,LawrenceRoy,RiteshSharma,andEugeneZhang DiscretePoincaréDualityAnglesasShapeSignaturesonSimplicial SurfaceswithBoundary......................................................... 251 KonstantinPoelkeandKonradPolthier Index............................................................................... 265