Source author record

Ali D. Mehrabi

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

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Minimum Perimeter-Sum Partitions in the Plane

Let $P$ be a set of $n$ points in the plane. We consider the problem of partitioning $P$ into two subsets $P_1$ and $P_2$ such that the sum of the perimeters of $\text{CH}(P_1)$ and $\text{CH}(P_2)$ is minimized, where $\text{CH}(P_i)$ denotes the convex hull of $P_i$ . The problem was first studied by Mitchell and Wynters in 1991 who gave an $O(n^2)$ time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in $O(n \log^2 n)$ time and a $(1+\varepsilon)$ -approximation algorithm running in $O(n + 1/\varepsilon^2\cdot\log^2(1/\varepsilon))$ time.

preprint2015arXiv

Finding Pairwise Intersections Inside a Query Range

We study the following problem: preprocess a set O of objects into a data structure that allows us to efficiently report all pairs of objects from O that intersect inside an axis-aligned query range Q. We present data structures of size $O(n({\rm polylog} n))$ and with query time $O((k+1)({\rm polylog} n))$ time, where k is the number of reported pairs, for two classes of objects in the plane: axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in R^3, we present a data structures of size $O(n\sqrt{n}({\rm polylog} n))$ and query time $O((\sqrt{n}+k)({\rm polylog} n))$ . When the objects and query are fat, we obtain $O((k+1)({\rm polylog} n))$ query time using $O(n({\rm polylog} n))$ storage.

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.