Persistence Algorithm Takes Cubic Time in Worst Case. Morozov, D. abstract bibtex Given a sequence of N simplices, we consider the sequence of sets Ki consisting of the first i simplices, for 1 ≤ i ≤ N. We call the sequence of Ki a filtration if all the Ki are simplicial complexes. In this note, we describe a filtration of a simplicial complex of N simplices on which the algorithm Pair-Simplices of Edelsbrunner, Letscher and Zomorodian [1] performs Ω(N 3) operations. The existence of this filtration should be contrasted to the experimentally observed only slightly super-linear running time for filtrations that arise from applications. We describe the space as well as the ordering on the simplices. Let n = ⌊(N + 29)/7⌋, v = ⌊(n − 1)/2⌋, and note that both n and v are in Ω(N). In our filtration, all vertices appear before all edges in the filtration, and all edges appear before all triangles. The indices that we assign to the simplices will be within their respective classes (e.g., edge labeled n will appear before the triangle labeled 1). Some edges will receive a negative index, which is done for simplicity to indicate that they appear before the edges with positive labels (see Figure 2). Figure 1 illustrates the construction of our space as well as the assignment of indices to the simplices. Starting with triangle ABC, we add v vertices inside the triangle in the following manner: we place the first vertex V1 near the middle of edge AB, the second vertex V2 near the middle of
@article{morozovPersistenceAlgorithmTakes2005,
title = {Persistence Algorithm Takes Cubic Time in Worst Case},
abstract = {Given a sequence of N simplices, we consider the sequence of sets Ki consisting of the first i simplices, for 1 ≤ i ≤ N. We call the sequence of Ki a filtration if all the Ki are simplicial complexes. In this note, we describe a filtration of a simplicial complex of N simplices on which the algorithm Pair-Simplices of Edelsbrunner, Letscher and Zomorodian [1] performs Ω(N 3) operations. The existence of this filtration should be contrasted to the experimentally observed only slightly super-linear running time for filtrations that arise from applications. We describe the space as well as the ordering on the simplices. Let n = ⌊(N + 29)/7⌋, v = ⌊(n − 1)/2⌋, and note that both n and v are in Ω(N). In our filtration, all vertices appear before all edges in the filtration, and all edges appear before all triangles. The indices that we assign to the simplices will be within their respective classes (e.g., edge labeled n will appear before the triangle labeled 1). Some edges will receive a negative index, which is done for simplicity to indicate that they appear before the edges with positive labels (see Figure 2). Figure 1 illustrates the construction of our space as well as the assignment of indices to the simplices. Starting with triangle ABC, we add v vertices inside the triangle in the following manner: we place the first vertex V1 near the middle of edge AB, the second vertex V2 near the middle of},
journaltitle = {BioGeometry News, Dept. Comput. Sci., Duke Univ},
date = {2005},
author = {Morozov, Dmitriy},
file = {/home/dimitri/Nextcloud/Zotero/storage/I6HKHZQ5/Morozov - 2005 - Persistence algorithm takes cubic time in worst ca.pdf;/home/dimitri/Nextcloud/Zotero/storage/WN8ZVZH9/summary.html}
}
Downloads: 0
{"_id":"p8T3ksranXHoz3ENZ","bibbaseid":"morozov-persistencealgorithmtakescubictimeinworstcase","authorIDs":[],"author_short":["Morozov, D."],"bibdata":{"bibtype":"article","type":"article","title":"Persistence Algorithm Takes Cubic Time in Worst Case","abstract":"Given a sequence of N simplices, we consider the sequence of sets Ki consisting of the first i simplices, for 1 ≤ i ≤ N. We call the sequence of Ki a filtration if all the Ki are simplicial complexes. In this note, we describe a filtration of a simplicial complex of N simplices on which the algorithm Pair-Simplices of Edelsbrunner, Letscher and Zomorodian [1] performs Ω(N 3) operations. The existence of this filtration should be contrasted to the experimentally observed only slightly super-linear running time for filtrations that arise from applications. We describe the space as well as the ordering on the simplices. Let n = ⌊(N + 29)/7⌋, v = ⌊(n − 1)/2⌋, and note that both n and v are in Ω(N). In our filtration, all vertices appear before all edges in the filtration, and all edges appear before all triangles. The indices that we assign to the simplices will be within their respective classes (e.g., edge labeled n will appear before the triangle labeled 1). Some edges will receive a negative index, which is done for simplicity to indicate that they appear before the edges with positive labels (see Figure 2). Figure 1 illustrates the construction of our space as well as the assignment of indices to the simplices. Starting with triangle ABC, we add v vertices inside the triangle in the following manner: we place the first vertex V1 near the middle of edge AB, the second vertex V2 near the middle of","journaltitle":"BioGeometry News, Dept. Comput. Sci., Duke Univ","date":"2005","author":[{"propositions":[],"lastnames":["Morozov"],"firstnames":["Dmitriy"],"suffixes":[]}],"file":"/home/dimitri/Nextcloud/Zotero/storage/I6HKHZQ5/Morozov - 2005 - Persistence algorithm takes cubic time in worst ca.pdf;/home/dimitri/Nextcloud/Zotero/storage/WN8ZVZH9/summary.html","bibtex":"@article{morozovPersistenceAlgorithmTakes2005,\n title = {Persistence Algorithm Takes Cubic Time in Worst Case},\n abstract = {Given a sequence of N simplices, we consider the sequence of sets Ki consisting of the first i simplices, for 1 ≤ i ≤ N. We call the sequence of Ki a filtration if all the Ki are simplicial complexes. In this note, we describe a filtration of a simplicial complex of N simplices on which the algorithm Pair-Simplices of Edelsbrunner, Letscher and Zomorodian [1] performs Ω(N 3) operations. The existence of this filtration should be contrasted to the experimentally observed only slightly super-linear running time for filtrations that arise from applications. We describe the space as well as the ordering on the simplices. Let n = ⌊(N + 29)/7⌋, v = ⌊(n − 1)/2⌋, and note that both n and v are in Ω(N). In our filtration, all vertices appear before all edges in the filtration, and all edges appear before all triangles. The indices that we assign to the simplices will be within their respective classes (e.g., edge labeled n will appear before the triangle labeled 1). Some edges will receive a negative index, which is done for simplicity to indicate that they appear before the edges with positive labels (see Figure 2). Figure 1 illustrates the construction of our space as well as the assignment of indices to the simplices. Starting with triangle ABC, we add v vertices inside the triangle in the following manner: we place the first vertex V1 near the middle of edge AB, the second vertex V2 near the middle of},\n journaltitle = {BioGeometry News, Dept. Comput. Sci., Duke Univ},\n date = {2005},\n author = {Morozov, Dmitriy},\n file = {/home/dimitri/Nextcloud/Zotero/storage/I6HKHZQ5/Morozov - 2005 - Persistence algorithm takes cubic time in worst ca.pdf;/home/dimitri/Nextcloud/Zotero/storage/WN8ZVZH9/summary.html}\n}\n\n","author_short":["Morozov, D."],"key":"morozovPersistenceAlgorithmTakes2005","id":"morozovPersistenceAlgorithmTakes2005","bibbaseid":"morozov-persistencealgorithmtakescubictimeinworstcase","role":"author","urls":{},"downloads":0},"bibtype":"article","biburl":"https://raw.githubusercontent.com/dlozeve/newblog/master/bib/all.bib","creationDate":"2020-01-08T20:39:39.170Z","downloads":0,"keywords":[],"search_terms":["persistence","algorithm","takes","cubic","time","worst","case","morozov"],"title":"Persistence Algorithm Takes Cubic Time in Worst Case","year":null,"dataSources":["3XqdvqRE7zuX4cm8m"]}