Source author record

Sepideh Aghamolaei

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

4works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

A Data-Structure for Approximate Longest Common Subsequence of A Set of Strings

Given a set of $k$ strings $I$ , their longest common subsequence (LCS) is the string with the maximum length that is a subset of all the strings in $I$ . A data-structure for this problem preprocesses $I$ into a data-structure such that the LCS of a set of query strings $Q$ with the strings of $I$ can be computed faster. Since the problem is NP-hard for arbitrary $k$ , we allow an error that allows some characters to be replaced by other characters. We define the approximation version of the problem with an extra input $m$ , which is the length of the regular expression (regex) that describes the input, and the approximation factor is the logarithm of the number of possibilities in the regex returned by the algorithm, divided by the logarithm regex with the minimum number of possibilities. Then, we use a tree data-structure to achieve sublinear-time LCS queries. We also explain how the idea can be extended to the longest increasing subsequence (LIS) problem.

preprint2021arXiv

Catching a Polygonal Fish with a Minimum Net

Given a polygon $P$ in the plane that can be translated, rotated and enlarged arbitrarily inside a unit square, the goal is to find a set of lines such that at least one of them always hits $P$ and the number of lines is minimized. We prove the solution is always a regular grid or a set of equidistant parallel lines, whose distance depends on $P$ .

preprint2021arXiv

Symmetries: From Proofs To Algorithms And Back

We call an objective function or algorithm symmetric with respect to an input if after swapping two parts of the input in any algorithm, the solution of the algorithm and the output remain the same. More formally, for a permutation $π$ of an indexed input, and another permutation $π'$ of the same input, such that swapping two items converts $π$ to $π'$ , $f(π)=f(π')$ , where $f$ is the objective function. After reviewing samples of the algorithms that exploit symmetry, we give several new ones, for finding lower-bounds, beating adversaries in online algorithms, designing parallel algorithms and data summarization. We show how to use the symmetry between the sampled points to get a lower/upper bound on the solution. This mostly depends on the equivalence class of the parts of the input that when swapped, do not change the solution or its cost.

preprint2020arXiv

Computing The Packedness of Curves

A polygonal curve $P$ with $n$ vertices is $c$ -packed, if the sum of the lengths of the parts of the edges of the curve that are inside any disk of radius $r$ is at most $cr$ , for any $r>0$ . Similarly, the concept of $c$ -packedness can be defined for any scaling of a given shape. Assuming $L$ is the diameter of $P$ and $δ$ is the minimum distance between points on disjoint edges of $P$ , we show the approximation factor of the existing $O(\frac{\log (L/δ)}εn^3)$ time algorithm is $1+ε$ -approximation algorithm. The massively parallel versions of these algorithms run in $O(\log (L/δ))$ rounds. We improve the existing $O((\frac{n}{ε^3})^{\frac 4 3}\polylog \frac n ε)$ time $(6+ε)$ -approximation algorithm by providing a $(4+ε)$ -approximation $O(n(\log^2 n)(\log^2 \frac{1}ε)+\frac{n}ε)$ time algorithm, and the existing $O(n^2)$ time $2$ -approximation algorithm improving the existing $O(n^2\log n)$ time $2$ -approximation algorithm. Our exact $c$ -packedness algorithm takes $O(n^5)$ time, which is the first exact algorithm for disks. We show using $α$ -fat shapes instead of disks adds a factor $α^2$ to the approximation. We also give a data-structure for computing the curve-length inside query disks. It has $O(n^6\log n)$ construction time, uses $O(n^6)$ space, and has query time $O(\log n+k)$ , where $k$ is the number of intersected segments with the query shape. We also give a massively parallel algorithm for relative $c$ -packedness with $O(1)$ rounds.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Sepideh Aghamolaei

Research overview

Is this your work?

4 publications

A Data-Structure for Approximate Longest Common Subsequence of A Set of Strings

Catching a Polygonal Fish with a Minimum Net

Symmetries: From Proofs To Algorithms And Back

Computing The Packedness of Curves

See the researcher in context

Building this map preview