My name is Mahmoodreza Jahanseir. I am a PhD candidate in Computer Science Department at the University of Connecticut. I am fortunate to have professor Donald Sheehy as my advisor. I am interested in design and analysis of algorithms and data structures. My research mainly focuses on computational geometry and topological data analysis. Currently, I am working on data structures for general metric spaces. I received my Master's degree in Computer Engineering from Amirkabir University of Technology in Iran.

Email: reza At engr Dot uconn Dot edu

A Geometric Perspective on Sparse Filtrations
Given a finite data set in a Euclidean space, it is natural to consider the balls around the data points as a way to fill in the space around the data and give an estimate of the missing data. The union of balls is often called the offsets of the point set. Persistent homology was originally invented as a way to study the changes in topology of the offsets of a point set as the radius increases from $0$ to $\infty$. The input to persistent homology is usually a filtered simplicial complex, that is, an ordered collection of simplices (vertices, edges, triangles, etc.) such that each simplex appears only after its boundary simplices of one dimension lower.
A point set sampled on a sphere, its offsets, and its (sparsified) nerve complex.
The Nerve Theorem and its persistent variant allow one to compute the persistent homology of the offsets by instead looking at a discrete object, a filtered simplicial complex called the nerve. The simplest version of this complex is called the Cech complex and it may be viewed as the set of all subsets of the input, ordered by the radius of their smallest enclosing ball. Naturally, the Cech complex gets very big very fast, even when restricting to subsets of constant size. A common alternative is the Rips complex but it suffers similar difficulties. Over the last few years, there have been several approaches to building sparser complexes that still give good approximations to the persistent homology.
We propose a simpler explanation for the construction and proof of correctness of sparse filtrations. Our new geometric construction shows that the sparse complex is just a nerve in one dimension higher. The approach easily generalizes to Rips, Cech and related complexes (the offsets for any convex metric). This is another advantage of the geometric view as the main result follows from convexity rather than explicit construction of simplicial map homotopy equivalences. We present efficient algorithms for computing the edges of a sparse filtration in linear time, their birth times, and subsequently the $k$-simplices from a greedy permutation. We also present a simple geometric proof that the explicit removal of vertices from the sparse filtration can be done with edge contractions. This can be done without resorting to the full-fledged zigzag persistence algorithm or even the full simplicial map persistence algorithm.

In the following, you can interactively work with a data set sampled on a sphere. In this demo, green and blue balls show perturbed and unperturbed offsets, respectively. source code
Drag and drop: Rotation
Up: Zoom-in
Down: Zoom-out
b: Offsets
c: Simplicial complex
s: Sparsify
1: 1-skeleton
2: 2-simplices
x: Auto rotate w.r.t $x$-axis
y: Auto rotate w.r.t $y$-axis
a: Auto increase
Conferences
Transforming Hierarchical Trees on Metric Spaces
Mahmoodreza Jahanseir, Donald Sheehy
The 28th Canadian Conference on Computational Geometry, Vancouver, August, 2016

PDF

Abstract

Bibtex

We show how a simple hierarchical tree called a cover tree can be turned into an asymptotically more efficient one known as a net-tree in linear time. We also introduce two linear-time operations to manipulate cover trees called coarsening and refining. These operations make a trade-off between tree height and the node degree.

@inproceedings{jahanseir16transforming,

Author = {Mahmoodreza Jahanseir and Donald R. Sheehy},

Title = {Transforming Hierarchical Trees on Metric Spaces},

Booktitle = {Proceedings of the Canadian Conference on Computational Geometry},

Year = {2016},

A Geometric Perspective on Sparse Filtrations
Nicholas Cavanna, Mahmoodreza Jahanseir, Donald Sheehy
The 27th Canadian Conference on Computational Geometry, Kingston, August, 2015

PDF

arXiv

Abstract

Bibtex

We present a geometric perspective on sparse filtrations used in topological data analysis. This new perspective leads to much simpler proofs, while also being more general, applying equally to Rips filtrations and Cech filtrations for any convex metric. We give an algorithm for finding the simplices in such a filtration directly from a greedy permutation. The vertex removal in such filtrations is proven to be implementable as a sequence of elementary edge contractions.

@inproceedings{cavanna15geometric,

Author = {Nicholas J. Cavanna and Mahmoodreza Jahanseir and Donald R. Sheehy},

Title = {A Geometric Perspective on Sparse Filtrations},

Booktitle = {Proceedings of the Canadian Conference on Computational Geometry},

Year = {2015},

Visualizing Sparse Filtrations
Nicholas Cavanna, Mahmoodreza Jahanseir, Donald Sheehy
The 31st International Symposium on Computational Geometry: Multimedia Exposition, Eindhoven, June, 2015

PDF

Video

Abstract

Bibtex

Over the last few years, there have been several approaches to building sparser complexes that still give good approximations to the persistent homology. In this video, we have illustrated a geometric perspective on sparse filtrations that leads to simpler proofs, more general theorems, and a more visual explanation. We hope that as these techniques become easier to understand, they will also become easier to use.

@inproceedings{cavanna15visualizing,

Author = {Nicholas J. Cavanna and Mahmoodreza Jahanseir and Donald R. Sheehy},

Title = {Visualizing Sparse Filtrations},

Booktitle = {Proceedings of the 31st International Symposium on Computational Geometry},

Year = {2015},

Location = {Eindhoven, Netherlands}}

Heuristic algorithms for geometric embedding of complete binary trees onto a point set
Mehrab Norouzitallab, Alireza Bagheri, Mahmoodreza Jahanseir
The International MultiConference of Engineers and Computer Scientists, Hong Kong, March, 2014

PDF

Abstract

Bibtex

In the geometric graph embedding problem, a graph with n vertices and a set of $n$ points in the plane are given, and the aim of embedding is to find a mapping between vertices of the graph to these points in such a way that minimizes the length of the embedded graph on the point set. Since the travelling salesman problem is a special case of the graph embedding problem, therefore, the problem is an NP-hard problem. In this paper, we consider a particular case where the given graph is a binary tree. We present four heuristic approaches, then we compare the time complexity, and the resulted embedding length of these algorithms.

@inproceedings{norouzitallab14heuristic,

Author = {Mehrab Norouzitallab, Alireza Bagheri, Mahmoodreza Jahanseir},

Title = {Heuristic algorithms for geometric embedding of complete binary trees onto a point set},

Booktitle = {Proceedings of the International MultiConference of Engineers and Computer Scientists},

Year = {2014},

Location = {Hong Kong}}

Workshops
Randomized Incremental Construction of Net-Trees
Mahmoodreza Jahanseir, Donald Sheehy
The 27th Fall Workshop on Computational Geometry, Stony Brook, October, 2017

PDF

Constructing Hierarchical Trees from Locally Greedy Permutations
Mahmoodreza Jahanseir, Donald Sheehy
The 26th Fall Workshop on Computational Geometry, New York, October, 2016

PDF

Transforming Hierarchical Trees on Metric Spaces
Mahmoodreza Jahanseir, Donald Sheehy
The 32nd International Symposium on Computational Geometry: Young Researcher Forum, Boston, June, 2016

PDF

From Cover Trees to Net-trees
Mahmoodreza Jahanseir, Donald Sheehy
The 25th Fall Workshop on Computational Geometry, Buffalo, October, 2015

PDF

Randomized Incremental Construction of Net-Trees
Mahmoodreza Jahanseir, Donald Sheehy
The 27th Fall Workshop on Computational Geometry, Stony Brook, October, 2017
Hierarchical Metric Trees for Topological Data Analysis
Mahmoodreza Jahanseir, Donald Sheehy
SIAM Conference on Industrial and Applied Geometry, Pittsburgh, July, 2017
Constructing Hierarchical Trees from Locally Greedy Permutations
Mahmoodreza Jahanseir, Donald Sheehy
The 26th Fall Workshop on Computational Geometry, New York, October, 2016
Transforming Hierarchical Trees on Metric Spaces
The 32nd International Symposium on Computational Geometry: Young Researcher Forum, Boston, June, 2016.
From Cover Trees to Net-trees
Fall Workshop on Computational Geometry, Buffalo, October, 2015.