# Parallel Computation of the Topology of Level Sets

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2004-01

AUTHORS ABSTRACT

This paper introduces two efficient algorithms that compute the Contour Tree of a three-dimensional scalar field F and its augmented version with the Betti numbers of each isosurface. The Contour Tree is a fundamental data structure in scientific visualization that is used to pre-process the domain mesh to allow optimal computation of isosurfaces with minimal overhead storage. The Contour Tree can also be used to build user interfaces reporting the complete topological characterization of a scalar field, as shown in Figure~\ref{fig:top}. Data exploration time is reduced since the user understands the evolution of level set components with changing isovalue. The Augmented Contour Tree provides even more accurate information segmenting the range space of the scalar field into regions of invariant topology. The exploration time for a single isosurface is also improved since its genus is known in advance. Our first new algorithm augments any given Contour Tree with the Betti numbers of all possible corresponding isocontours in linear time with the size of the tree. Moreover, we show how to extend the scheme introduced in [3] with the Betti number computation without increasing its complexity. Thus, we improve on the time complexity in our previous approach from O(m log m) to O(n log n + m), where m is the number of cells and n is the number of vertices in the domain of F. Our second contribution is a new divide-and-conquer algorithm that computes the Augmented Contour Tree with improved efficiency. The approach computes the output Contour Tree by merging two intermediate Contour Trees and is independent of the interpolant. In this way we confine any knowledge regarding a specific interpolant to an independent function that computes the tree for a single cell. We have implemented this function for the trilinear interpolant and plan to replace it with higher-order interpolants when needed. The time complexity is O(n + t log n), where t is the number of critical points of F. For the first time we can compute the Contour Tree in linear time in many practical cases where t = O(n1–ε). We report the running times for a parallel implementation, showing good scalability with the number of processors. More... »

PAGES

249-268

TITLE

Algorithmica

ISSUE

1

VOLUME

38

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-003-1052-3

DOI

http://dx.doi.org/10.1007/s00453-003-1052-3

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1026752183

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Lawrence Livermore National Laboratory",
"id": "https://www.grid.ac/institutes/grid.250008.f",
"name": [
"Center of Applied Scientific Computing,\nLawrence Livermore National Laboratory, Box 808, L-560, Livermore,\nCA 94551, USA"
],
"type": "Organization"
},
"familyName": "Pascucci",
"givenName": "Valerio",
"id": "sg:person.01072426252.83",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01072426252.83"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Lawrence Livermore National Laboratory",
"id": "https://www.grid.ac/institutes/grid.250008.f",
"name": [
"Center of Applied Scientific Computing,\nLawrence Livermore National Laboratory, Box 808, L-560, Livermore,\nCA 94551, USA"
],
"type": "Organization"
},
"familyName": "Cole-McLaughlin",
"givenName": "Kree",
"id": "sg:person.014753171511.37",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014753171511.37"
],
"type": "Person"
}
],
"datePublished": "2004-01",
"datePublishedReg": "2004-01-01",
"description": "This paper introduces two efficient algorithms that compute the Contour Tree of a three-dimensional scalar field F and its augmented version with the Betti numbers of each isosurface. The Contour Tree is a fundamental data structure in scientific visualization that is used to pre-process the domain mesh to allow optimal computation of isosurfaces with minimal overhead storage. The Contour Tree can also be used to build user interfaces reporting the complete topological characterization of a scalar field, as shown in Figure~\\ref{fig:top}. Data exploration time is reduced since the user understands the evolution of level set components with changing isovalue. The Augmented Contour Tree provides even more accurate information segmenting the range space of the scalar field into regions of invariant topology. The exploration time for a single isosurface is also improved since its genus is known in advance. Our first new algorithm augments any given Contour Tree with the Betti numbers of all possible corresponding isocontours in linear time with the size of the tree. Moreover, we show how to extend the scheme introduced in [3] with the Betti number computation without increasing its complexity. Thus, we improve on the time complexity in our previous approach from O(m log m) to O(n log n + m), where m is the number of cells and n is the number of vertices in the domain of F. Our second contribution is a new divide-and-conquer algorithm that computes the Augmented Contour Tree with improved efficiency. The approach computes the output Contour Tree by merging two intermediate Contour Trees and is independent of the interpolant. In this way we confine any knowledge regarding a specific interpolant to an independent function that computes the tree for a single cell. We have implemented this function for the trilinear interpolant and plan to replace it with higher-order interpolants when needed. The time complexity is O(n + t log n), where t is the number of critical points of F. For the first time we can compute the Contour Tree in linear time in many practical cases where t = O(n1\u2013\u03b5). We report the running times for a parallel implementation, showing good scalability with the number of processors.",
"genre": "research_article",
"id": "sg:pub.10.1007/s00453-003-1052-3",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"name": "Parallel Computation of the Topology of Level Sets",
"pagination": "249-268",
"productId": [
{
"type": "PropertyValue",
"value": [
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-003-1052-3"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1026752183"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-003-1052-3",
"https://app.dimensions.ai/details/publication/pub.1026752183"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-10T19:09",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8678_00000513.jsonl",
"type": "ScholarlyArticle",
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-003-1052-3'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-003-1052-3'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-003-1052-3'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-003-1052-3'

This table displays all metadata directly associated to this object as RDF triples.

68 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N692966b25b2d498da200bd27ca3f0984
4 schema:datePublished 2004-01
5 schema:datePublishedReg 2004-01-01
6 schema:description This paper introduces two efficient algorithms that compute the Contour Tree of a three-dimensional scalar field F and its augmented version with the Betti numbers of each isosurface. The Contour Tree is a fundamental data structure in scientific visualization that is used to pre-process the domain mesh to allow optimal computation of isosurfaces with minimal overhead storage. The Contour Tree can also be used to build user interfaces reporting the complete topological characterization of a scalar field, as shown in Figure~\ref{fig:top}. Data exploration time is reduced since the user understands the evolution of level set components with changing isovalue. The Augmented Contour Tree provides even more accurate information segmenting the range space of the scalar field into regions of invariant topology. The exploration time for a single isosurface is also improved since its genus is known in advance. Our first new algorithm augments any given Contour Tree with the Betti numbers of all possible corresponding isocontours in linear time with the size of the tree. Moreover, we show how to extend the scheme introduced in [3] with the Betti number computation without increasing its complexity. Thus, we improve on the time complexity in our previous approach from O(m log m) to O(n log n + m), where m is the number of cells and n is the number of vertices in the domain of F. Our second contribution is a new divide-and-conquer algorithm that computes the Augmented Contour Tree with improved efficiency. The approach computes the output Contour Tree by merging two intermediate Contour Trees and is independent of the interpolant. In this way we confine any knowledge regarding a specific interpolant to an independent function that computes the tree for a single cell. We have implemented this function for the trilinear interpolant and plan to replace it with higher-order interpolants when needed. The time complexity is O(n + t log n), where t is the number of critical points of F. For the first time we can compute the Contour Tree in linear time in many practical cases where t = O(n1–ε). We report the running times for a parallel implementation, showing good scalability with the number of processors.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N30394be05ef14d999093c209a48ea182
11 N6d0b8323d955477aacdf169dae24b685
12 sg:journal.1047644
13 schema:name Parallel Computation of the Topology of Level Sets
14 schema:pagination 249-268
15 schema:productId N12f6e810ddf54863a163ac444d9bfe55
16 N5052c52455dc4d20ac29c681a81ccbb4
17 N9dfc4c45e5d349a4b08e8ebbc9856a81
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026752183
19 https://doi.org/10.1007/s00453-003-1052-3
20 schema:sdDatePublished 2019-04-10T19:09
22 schema:sdPublisher N1597e614f5ff4a2a892029275f892408
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N12f6e810ddf54863a163ac444d9bfe55 schema:name dimensions_id
28 schema:value pub.1026752183
29 rdf:type schema:PropertyValue
30 N1597e614f5ff4a2a892029275f892408 schema:name Springer Nature - SN SciGraph project
31 rdf:type schema:Organization
33 rdf:type schema:PublicationVolume
34 N4114366a4e3d45a09ce06972358e890c rdf:first sg:person.014753171511.37
35 rdf:rest rdf:nil
38 rdf:type schema:PropertyValue
39 N692966b25b2d498da200bd27ca3f0984 rdf:first sg:person.01072426252.83
40 rdf:rest N4114366a4e3d45a09ce06972358e890c
41 N6d0b8323d955477aacdf169dae24b685 schema:issueNumber 1
42 rdf:type schema:PublicationIssue
43 N9dfc4c45e5d349a4b08e8ebbc9856a81 schema:name doi
44 schema:value 10.1007/s00453-003-1052-3
45 rdf:type schema:PropertyValue
46 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
47 schema:name Information and Computing Sciences
48 rdf:type schema:DefinedTerm
49 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
50 schema:name Computation Theory and Mathematics
51 rdf:type schema:DefinedTerm
52 sg:journal.1047644 schema:issn 0178-4617
53 1432-0541
54 schema:name Algorithmica
55 rdf:type schema:Periodical
56 sg:person.01072426252.83 schema:affiliation https://www.grid.ac/institutes/grid.250008.f
57 schema:familyName Pascucci
58 schema:givenName Valerio
59 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01072426252.83
60 rdf:type schema:Person
61 sg:person.014753171511.37 schema:affiliation https://www.grid.ac/institutes/grid.250008.f
62 schema:familyName Cole-McLaughlin
63 schema:givenName Kree
64 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014753171511.37
65 rdf:type schema:Person
66 https://www.grid.ac/institutes/grid.250008.f schema:alternateName Lawrence Livermore National Laboratory
67 schema:name Center of Applied Scientific Computing, Lawrence Livermore National Laboratory, Box 808, L-560, Livermore, CA 94551, USA
68 rdf:type schema:Organization