17 citations · 32 across the 18 of their papers we have counts for
15 papers · 1 filter
Compatible Triangulations of Simple Polygons
Peyman Afshani, Boris Aronov, Kevin Buchin +5
Let and be simple polygons with vertices each. We wish to compute triangulations of and that are combinatorially equivalent, if they exist. We consider two vers…
Convexity Helps Iterated Search in 3D
Peyman Afshani, Yakov Nekrich, Frank Staals
Inspired by the classical fractional cascading technique, we introduce new techniques to speed up the following type of iterated search in 3D: The input is a graph wit…
Property Testing of Curve Similarity
Peyman Afshani, Maike Buchin, Anne Driemel +2
We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is giv…
On Range Summary Queries
Peyman Afshani, Pingan Cheng, Aniket Basu Roy +1
We study the query version of the approximate heavy hitter and quantile problems. In the former problem, the input is a parameter and a set of points in $\mat…
Lower Bounds for Intersection Reporting among Flat Objects
Peyman Afshani, Pingan Cheng
Recently, Ezra and Sharir [ES22a] showed an space and query time data structure for ray shooting among triangles in . This improves the…
An Optimal Lower Bound for Simplex Range Reporting
Peyman Afshani, Pingan Cheng
We give a simplified and improved lower bound for the simplex range reporting problem. We show that given a set of points in , any data structure that uses $S…
On Semialgebraic Range Reporting
Peyman Afshani, Pingan Cheng
In the problem of semialgebraic range searching, we are to preprocess a set of points in such that the subset of points inside a semialgebraic region described by $O…
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 of sites in a metric space and a set of robots with the same maximum speed, compute a patrol schedule of min…
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
Peyman Afshani, Pingan Cheng
In the semialgebraic range searching problem, we are to preprocess points in s.t. for any query range from a family of constant complexity semialgebraic sets, al…
2D Fractional Cascading on Axis-aligned Planar Subdivisions
Peyman Afshani, Pingan Cheng
Fractional cascading is one of the influential techniques in data structures, as it provides a general framework for solving the important iterative search problem. In the problem,…
On the complexity of range searching among curves
Peyman Afshani, Anne Driemel
Modern tracking technology has made the collection of large numbers of densely sampled trajectories of moving objects widely available. We consider a fundamental problem encountere…
Applications of incidence bounds in point covering problems
Peyman Afshani, Edvin Berglin, Ingo van Duijn +1
In the Line Cover problem a set of n points is given and the task is to cover the points using either the minimum number of lines or at most k lines. In Curve Cover, a generalizati…
Approximating the Simplicial Depth
Peyman Afshani, Donald R. Sheehy, Yannik Stein
Let be a set of points in -dimensions. The simplicial depth, of a point is the number of -simplices with vertices in that contain in their convex…
Instance Optimal Geometric Algorithms
Peyman Afshani, Jérémy Barbay, Timothy Chan
We prove the existence of an algorithm for computing 2-d or 3-d convex hulls that is optimal for every point set in the following sense: for every sequence of points an…
Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions
Peyman Afshani, Hamed Hatami
We prove algorithmic and hardness results for the problem of finding the largest set of a fixed diameter in the Euclidean space. In particular, we prove that if is the larges…