Source author record

Saeed 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 Discrete Mathematics math.CO

Catalog footprint

Research overview

12works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

(Faster) Multi-Sided Boundary Labelling

A 1-bend boundary labelling problem consists of an axis-aligned rectangle $B$ , $n$ points (called sites) in the interior, and $n$ points (called ports) on the labels along the boundary of $B$ . The goal is to find a set of $n$ axis-aligned curves (called leaders), each having at most one bend and connecting one site to one port, such that the leaders are pairwise disjoint. A 1-bend boundary labelling problem is $k$ -sided ( $1\leq k\leq 4$ ) if the ports appear on $k$ different sides of $B$ . Kindermann et al. ["Multi-Sided Boundary Labeling", Algorithmica, 76(1): 225-258, 2016] showed that the 1-bend three-sided and four-sided boundary labelling problems can be solved in $O(n^4)$ and $O(n^9)$ time, respectively. Bose et al. [SWAT, 12:1-12:14, 2018] improved the latter running time to $O(n^6)$ by reducing the problem to computing maximum independent set in an outerstring graph. In this paper, we improve both previous results by giving new algorithms with running times $O(n^3\log n)$ and $O(n^5)$ to solve the 1-bend three-sided and four-sided boundary labelling problems, respectively.

preprint2020arXiv

Maximum Bipartite Subgraph of Geometric Intersection Graphs

We study the Maximum Bipartite Subgraph (MBS) problem, which is defined as follows. Given a set $S$ of $n$ geometric objects in the plane, we want to compute a maximum-size subset $S'\subseteq S$ such that the intersection graph of the objects in $S'$ is bipartite. We first give a simple $O(n)$ -time algorithm that solves the MBS problem on a set of $n$ intervals. We also give an $O(n^2)$ -time algorithm that computes a near-optimal solution for the problem on circular-arc graphs. We show that the MBS problem is NP-hard on geometric graphs for which the maximum independent set is NP-hard (hence, it is NP-hard even on unit squares and unit disks). On the other hand, we give a PTAS for the problem on unit squares and unit disks. Moreover, we show fast approximation algorithms with small-constant factors for the problem on unit squares, unit disks and unit-height rectangles. Finally, we study a closely related geometric problem, called Maximum Triangle-free Subgraph (TFS), where the objective is the same as that of MBS except the intersection graph induced by the set $S'$ needs to be triangle-free only (instead of being bipartite).

preprint2020arXiv

Parameterized Complexity of Two-Interval Pattern Problem

A \emph{2-interval} is the union of two disjoint intervals on the real line. Two 2-intervals $D_1$ and $D_2$ are \emph{disjoint} if their intersection is empty (i.e., no interval of $D_1$ intersects any interval of $D_2$ ). There can be three different relations between two disjoint 2-intervals; namely, preceding ( $<$ ), nested ( $\sqsubset$ ) and crossing ( $\between$ ). Two 2-intervals $D_1$ and $D_2$ are called \emph{ $R$ -comparable} for some $R\in\{<,\sqsubset,\between\}$ , if either $D_1RD_2$ or $D_2RD_1$ . A set $\mathcal{D}$ of disjoint 2-intervals is $\mathcal{R}$ -comparable, for some $\mathcal{R}\subseteq\{<,\sqsubset,\between\}$ and $\mathcal{R}\neq\emptyset$ , if every pair of 2-intervals in $\mathcal{R}$ are $R$ -comparable for some $R\in\mathcal{R}$ . Given a set of 2-intervals and some $\mathcal{R}\subseteq\{<,\sqsubset,\between\}$ , the objective of the \emph{2-interval pattern problem} is to find a largest subset of 2-intervals that is $\mathcal{R}$ -comparable. The 2-interval pattern problem is known to be $W[1]$ -hard when $|\mathcal{R}|=3$ and $NP$ -hard when $|\mathcal{R}|=2$ (except for $\mathcal{R}=\{<,\sqsubset\}$ , which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing it to be $W[1]$ -hard for both $\mathcal{R}=\{\sqsubset,\between\}$ and $\mathcal{R}=\{<,\between\}$ (when parameterized by the size of an optimal solution); this answers an open question posed by Vialette [Encyclopedia of Algorithms, 2008].

preprint2016arXiv

1-Bend RAC Drawings of 1-Planar Graphs

A graph is 1-planar if it has a drawing where each edge is crossed at most once. A drawing is RAC (Right Angle Crossing) if the edges cross only at right angles. The relationships between 1-planar graphs and RAC drawings have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC drawable and graphs that have a straight-line RAC drawing but that are not 1-planar. Also, straight-line RAC drawings always exist for IC-planar graphs, a subclass of 1-planar graphs. One of the main questions still open is whether every 1-planar graph has a RAC drawing with at most one bend per edge. We positively answer this question.

preprint2016arXiv

On $r$ -Guarding Thin Orthogonal Polygons

Guarding a polygon with few guards is an old and well-studied problem in computational geometry. Here we consider the following variant: We assume that the polygon is orthogonal and thin in some sense, and we consider a point $p$ to guard a point $q$ if and only if the minimum axis-aligned rectangle spanned by $p$ and $q$ is inside the polygon. A simple proof shows that this problem is NP-hard on orthogonal polygons with holes, even if the polygon is thin. If there are no holes, then a thin polygon becomes a tree polygon in the sense that the so-called dual graph of the polygon is a tree. It was known that finding the minimum set of $r$ -guards is polynomial for tree polygons, but the run-time was $\tilde{O}(n^{17})$ . We show here that with a different approach the running time becomes linear, answering a question posed by Biedl et al. (SoCG 2011). Furthermore, the approach is much more general, allowing to specify subsets of points to guard and guards to use, and it generalizes to polygons with $h$ holes or thickness $K$ , becoming fixed-parameter tractable in $h+K$ .

preprint2016arXiv

On Guarding Orthogonal Polygons with Sliding Cameras

A sliding camera inside an orthogonal polygon $P$ is a point guard that travels back and forth along an orthogonal line segment $γ$ in $P$ . The sliding camera $g$ can see a point $p$ in $P$ if the perpendicular from $p$ onto $γ$ is inside $P$ . In this paper, we give the first constant-factor approximation algorithm for the problem of guarding $P$ with the minimum number of sliding cameras. Next, we show that the sliding guards problem is linear-time solvable if the (suitably defined) dual graph of the polygon has bounded treewidth. Finally, we study art gallery theorems for sliding cameras, thus, give upper and lower bounds in terms of the number of guards needed relative to the number of vertices $n$ .

preprint2016arXiv

Sliding k-Transmitters: Hardness and Approximation

A sliding k-transmitter in an orthogonal polygon P is a mobile guard that travels back and forth along an orthogonal line segment s inside P. It can see a point p in P if the perpendicular from p onto s intersects the boundary of P at most k times. We show that guarding an orthogonal polygon P with the minimum number of k-transmitters is NP-hard, for any fixed k>0, even if P is simple and monotone. Moreover, we give an O(1)-approximation algorithm for this problem.

preprint2016arXiv

Unique Set Cover on Unit Disks and Unit Squares

We study the Unique Set Cover problem on unit disks and unit squares. For a given set $P$ of $n$ points and a set $D$ of $m$ geometric objects both in the plane, the objective of the Unique Set Cover problem is to select a subset $D'\subseteq D$ of objects such that every point in $P$ is covered by at least one object in $D'$ and the number of points covered uniquely is maximized, where a point is covered uniquely if the point is covered by exactly one object in $D'$ . In this paper, (i) we show that the Unique Set Cover is NP-hard on both unit disks and unit squares, and (ii) we give a PTAS for this problem on unit squares by applying the mod-one approach of Chan and Hu (Comput. Geom. 48(5), 2015).

preprint2015arXiv

A Note on Approximating 2-Transmitters

A k-transmitter in a simple orthogonal polygon P is a mobile guard that travels back and forth along an orthogonal line segment s inside P. The k-transmitter can see a point p in P if there exists a point q on s such that the line segment pq is normal to s and pq intersects the boundary of P in at most k points. In this paper, we give a 2-approximation algorithm for the problem of guarding a monotone orthogonal polygon with the minimum number of 2-transmitters.

preprint2015arXiv

Guarding the Vertices of an Orthogonal Terrain using Vertex Guards

A terrain T is an x-monotone polygonal chain in the plane; T is orthogonal if each edge of T is either horizontal or vertical. In this paper, we give an exact algorithm for the problem of guarding the convex vertices of an orthogonal terrain with the minimum number of reflex vertices.

preprint2013arXiv

A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras

Consider a sliding camera that travels back and forth along an orthogonal line segment $s$ inside an orthogonal polygon $P$ with $n$ vertices. The camera can see a point $p$ inside $P$ if and only if there exists a line segment containing $p$ that crosses $s$ at a right angle and is completely contained in $P$ . In the minimum sliding cameras (MSC) problem, the objective is to guard $P$ with the minimum number of sliding cameras. In this paper, we give an $O(n^{5/2})$ -time $(7/2)$ -approximation algorithm to the MSC problem on any simple orthogonal polygon with $n$ vertices, answering a question posed by Katz and Morgenstern (2011). To the best of our knowledge, this is the first constant-factor approximation algorithm for this problem.

preprint2013arXiv

New Hardness Results for Guarding Orthogonal Polygons with Sliding Cameras

Let $P$ be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment $s\in P$ as its \emph{trajectory}. The camera can see a point $p\in P$ if there exists a point $q\in s$ such that $pq$ is a line segment normal to $s$ that is completely inside $P$ . In the \emph{minimum-cardinality sliding cameras problem}, the objective is to find a set $S$ of sliding cameras of minimum cardinality to guard $P$ (i.e., every point in $P$ can be seen by some sliding camera) while in the \emph{minimum-length sliding cameras problem} the goal is to find such a set $S$ so as to minimize the total length of trajectories along which the cameras in $S$ travel. In this paper, we first settle the complexity of the minimum-length sliding cameras problem by showing that it is polynomial tractable even for orthogonal polygons with holes, answering a question asked by Katz and Morgenstern (2011). We next show that the minimum-cardinality sliding cameras problem is \textsc{NP}-hard when $P$ is allowed to have holes, which partially answers another question asked by Katz and Morgenstern (2011).

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.

Saeed Mehrabi

Research overview

Is this your work?

12 publications

(Faster) Multi-Sided Boundary Labelling

Maximum Bipartite Subgraph of Geometric Intersection Graphs

Parameterized Complexity of Two-Interval Pattern Problem

1-Bend RAC Drawings of 1-Planar Graphs

On $r$ -Guarding Thin Orthogonal Polygons

On Guarding Orthogonal Polygons with Sliding Cameras

Sliding k-Transmitters: Hardness and Approximation

Unique Set Cover on Unit Disks and Unit Squares

A Note on Approximating 2-Transmitters

Guarding the Vertices of an Orthogonal Terrain using Vertex Guards

A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras

New Hardness Results for Guarding Orthogonal Polygons with Sliding Cameras

See the researcher in context

Building this map preview

Saeed Mehrabi

Research overview

Is this your work?

12 publications

(Faster) Multi-Sided Boundary Labelling

Maximum Bipartite Subgraph of Geometric Intersection Graphs

Parameterized Complexity of Two-Interval Pattern Problem

1-Bend RAC Drawings of 1-Planar Graphs

On rrr-Guarding Thin Orthogonal Polygons

On Guarding Orthogonal Polygons with Sliding Cameras

Sliding k-Transmitters: Hardness and Approximation

Unique Set Cover on Unit Disks and Unit Squares

A Note on Approximating 2-Transmitters

Guarding the Vertices of an Orthogonal Terrain using Vertex Guards

A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras

New Hardness Results for Guarding Orthogonal Polygons with Sliding Cameras

See the researcher in context

Building this map preview

On $r$ -Guarding Thin Orthogonal Polygons