A. Nayyeri

activity

20142025

most citedMinimum cycle and homology bases of surface embedded graphs

7 citations · 14 across the 12 of their papers we have counts for

collaborators

Showing cs.CGShow all

9 papers · 1 filter

cs.CG2023

Topological $k$ -metrics

Willow Barkan-Vered, Huck Bennett, Amir Nayyeri

Metric spaces $(X, d)$ are ubiquitous objects in mathematics and computer science that allow for capturing (pairwise) distance relationships $d (x, y)$ between points $x, y \in X$ .…

cs.CG2022

ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth

Mitchell Black, Nello Blaser, Amir Nayyeri +1

Given a simplicial complex with $n$ simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected sur…

cs.CG2022

On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem

Peyman Afshani, Mark de Berg, Kevin Buchin +7

We consider the following surveillance problem: Given a set $P$ of $n$ sites in a metric space and a set of $k$ robots with the same maximum speed, compute a patrol schedule of min…

cs.CG2021

Finding minimum bounded and homologous chains in simplicial complexes with bounded-treewidth 1-skeleton

Mitchell Black, Amir Nayyeri

We consider two problems on simplicial complexes: the Optimal Bounded Chain Problem and the Optimal Homologous Chain Problem. The Optimal Bounded Chain Problem asks to find the min…

cs.CG2020

Minimum bounded chains and minimum homologous chains in embedded simplicial complexes

Glencora Borradaile, William Maxwell, Amir Nayyeri

We study two optimization problems on simplicial complexes with homology over $Z_{2}$ , the minimum bounded chain problem: given a $d$ -dimensional complex $K$ embed…

cs.CG2017

A Simple Algorithm for Computing a Cycle Separator

Sariel Har-Peled, Amir Nayyeri

We present a linear time algorithm for computing a cycle separator in a planar graph that is (arguably) simpler than previously known algorithms. Our algorithm builds on, and is so…

cs.CG2015

Approximating Nearest Neighbor Distances

Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller +3

Several researchers proposed using non-Euclidean metrics on point sets in Euclidean space for clustering noisy data. Almost always, a distance function is desired that recognizes t…

cs.CG2014

All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

Glencora Borradaile, David Eppstein, Amir Nayyeri +1

For an undirected $n$ -vertex graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$ , what is the weight of a minim…