Guarding Orthogonal Art Galleries with Sliding $k$-Transmitters: Hardness and Approximation
Abstract: A sliding $k$-transmitter inside an orthogonal polygon $P$, for a fixed $k\geq 0$, is a point guard that travels along an axis-parallel line segment $s$ in $P$. The sliding $k$-transmitter can see a point $p\in P$ if the perpendicular from $p$ onto $s$ intersects the boundary of $P$ in at most $k$ points. In the Minimum Sliding $k$-Transmitters (STk) problem, the objective is to guard $P$ with the minimum number of sliding $k$-transmitters. In this paper, we give a constant-factor approximation algorithm for the STk problem on
$P$ for any fixed $k\geq 0$. Moreover, we show that the ST0 problem is NP-hard on orthogonal polygons with holes even if only horizontal sliding 0-transmitters are allowed. For $k>0$, the problem is NP-hard even in the extremely restricted case where $P$ is simple and monotone. Finally, we study art gallery theorems; i.e., we give upper and lower bounds on the number of sliding transmitters required to guard $P$ relative to the number of vertices of $P$.
@article{journals/algorithmica/BiedlCLMMVY18,
author = {Therese Biedl and
Timothy M. Chan and
Stephanie Lee and
Saeed Mehrabi and
Fabrizio Montecchiani and
Hamideh Vosoughpour and
Darin Yu},
title = {Guarding Orthogonal Art Galleries with Sliding k-Transmitters: Hardness and Approximation},
journal = {Algorithmica},
year = {2018}
}
Computing Conforming Partitions of Orthogonal Polygons with Minimum Stabbing Number
Abstract: Let $P$ be an orthogonal polygon with $n$ vertices. A partition of $P$ into rectangles is called conforming if it results from cutting $P$ along a set of interior-disjoint line segments, each having both endpoints on the boundary of $P$. The stabbing number of a partition of $P$ into rectangles is the maximum number of rectangles stabbed by any orthogonal line segment inside $P$. In this paper, we consider the problem of finding a conforming partition of $P$ with minimum stabbing number. We first give an $O(n \log n)$-time algorithm to solve the problem when $P$ is a histogram. For an arbitrary orthogonal polygon (even with holes), we give an integer programming formulation of the problem and show that a simple rounding results in a 2-approximation algorithm for the problem. Finally, we show that the problem is NP-hard if $P$ is allowed to have holes.
Stephane Durocher, and
Saeed Mehrabi. Theoretical Computer Science. 689:157-168. 2017.
@article{journals/tcs/DurocherM17,
author = {Stephane Durocher and
Saeed Mehrabi},
title = {Computing conforming partitions of orthogonal polygons with minimum stabbing number},
journal = {Theor. Comput. Sci.},
volume = {689},
pages = {157--168},
year = {2017}
}
Guarding Orthogonal Art Galleries with Sliding Cameras
Abstract: A sliding camera in an orthogonal polygon $P$---that is, a polygon all of whose edges are axis-parallel---is a point guard $g$ that travels back and forth along an axis-parallel line segment $s$ inside $P$. A point $p$ in $P$ is guarded by $g$ if and only if there exists a point $q$ on $s$ such that line segment $pq$ is normal to $s$ and contained in $P$. In the minimum sliding cameras (MSC) problem, the objective is to guard $P$ with the minimum number of sliding cameras.
We give a dynamic programming algorithm that solves the MSC problem exactly on monotone orthogonal polygons in $O(n)$ time, improving the 2-approximation algorithm of Katz and Morgenstern (2011). More generally, our algorithm can be used to solve the MSC problem in $O(n)$ time on simple orthogonal polygons $P$ for which the dual graph induced by the vertical decomposition of $P$ is a path. Our results provide the first polynomial-time exact algorithms for the MSC problem on a non-trivial subclass of orthogonal polygons.
@article{journals/jda/BergDM17,
author = {Mark de Berg and
Stephane Durocher and
Saeed Mehrabi},
title = {Guarding monotone art galleries with sliding cameras in linear time},
journal = {J. Discrete Algorithms},
volume = {44},
pages = {39--47},
year = {2017}
}
On RAC Drawings of 1-Planar Graphs
Abstract: A drawing of a graph is 1-planar if each edge is crossed at most once. A graph is 1-planar if it has a 1-planar drawing. A $k$-bend RAC (Right Angle Crossing) drawing of a graph is a polyline drawing where each edge has at most $k$ bends and edges cross only at right angles. A graph is $k$-bend RAC if it has a $k$-bend RAC drawing. A 0-bend RAC graph (drawing) is also called a straight-line RAC graph (drawing). The relationships between 1-planar and $k$-bend RAC graphs have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC and straight-line RAC graphs that are not 1-planar. The existence of 1-planar straight-line RAC drawings has been proven only for restricted families of 1-planar graphs. Two of the main questions still open are: (i) What is the complexity of deciding whether a graph has a drawing that is both 1-planar and straight-line RAC? (ii) Does every 1-planar graph have a drawing that is both 1-planar and 1-bend RAC? In this paper we answer these two questions. Namely, we prove an NP-hardness result for the first question, and we positively answer the second question by describing a drawing algorithm for 1-planar graphs.
@article{journals/tcs/BekosDLMM17,
author = {Michael A. Bekos and
Walter Didimo and
Giuseppe Liotta and
Saeed Mehrabi and
Fabrizio Montecchiani},
title = {On {RAC} drawings of 1-planar graphs},
journal = {Theor. Comput. Sci.},
volume = {689},
pages = {48--57},
year = {2017}
}
Guarding Orthogonal Art Galleries with Sliding Cameras
Abstract: Let $P$ be an orthogonal polygon with $n$ vertices. A sliding camera travels back and forth along an orthogonal line segment $s\subseteq P$ corresponding to its trajectory. The camera sees a point $p\in P$ if there is a point $q\in s$ such that $pq$ is a line segment normal to $s$ that is completely contained in $P$. In the Minimum-Cardinality Sliding Cameras (MCSC) 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 in $S$), while in the Minimum-Length Sliding Cameras (MLSC) 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 answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP-complete when $P$ is allowed to have holes, and (iii) an $O(n^3 \log n)$-time 2-approximation algorithm for the MCSC problem on [NE]-star-shaped orthogonal polygons with $n$ vertices (similarly, [NW]-, [SE]-, or [SW]-star-shaped orthogonal polygons).
@article{journals/comgeo/DurocherFFMM17,
author = {Stephane Durocher and
Omrit Filtser and
Robert Fraser and
Ali D. Mehrabi and
Saeed Mehrabi},
title = {Guarding orthogonal art galleries with sliding cameras},
journal = {Comput. Geom.},
volume = {65},
pages = {12--26},
year = {2017}
}
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
Abstract: We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-logarithmic approximation is known for the problem and (perhaps surprisingly) the problem is NP-hard even when all the rectangles are ``anchored'' at a diagonal line with slope -1 (Pandit, CCCG 2017). In this paper, we first show that for any $\epsilon>0$, there exists a $(2+\epsilon)$-approximation algorithm for the MDS problem on ``diagonal-anchored'' rectangles, providing the first O(1)-approximation for the problem on a non-trivial subclass of rectangles. It is not hard to see that the MDS problem on ``diagonal-anchored'' rectangles is the same as the MDS problem on ``diagonal-anchored'' L-frames: the union of a vertical and a horizontal line segment that share an endpoint. As such, we also obtain a $(2+\epsilon)$-approximation for the problem with ``diagonal-anchored'' L-frames. On the other hand, we show that the problem is APX-hard in case the input L-frames intersect the diagonal, or the horizontal segments of the L-frames intersect a vertical line. However, as we show, the problem is linear-time solvable in case the L-frames intersect a vertical as well as a horizontal line. Finally, we consider the MDS problem in the so-called ``edge intersection model'' and obtain a number of results, answering two questions posed by Mehrabi (WAOA 2017).
Abstract: An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-line segment connecting the points corresponding to two vertices does not intersect any obstacles if and only if the vertices are adjacent in the graph. The obstacle representation and its plane variant (in which the resulting representation is a plane straight-line embedding of the graph) have been extensively studied with the main objective of minimizing the number of obstacles. Recently, Biedl and Mehrabi (GD 2017) studied non-blocking grid obstacle representations of graphs in which the vertices of the graph are mapped onto points in the plane while the straight-line segments representing the adjacency between the vertices is replaced by the $L_1$ (Manhattan) shortest paths in the plane that avoid obstacles.
In this paper, we introduce the notion of geodesic obstacle representations of graphs with the main goal of providing a generalized model, which comes naturally when viewing line segments as shortest paths in the Euclidean plane. To this end, we extend the definition of obstacle representation by allowing some obstacles-avoiding shortest path between the corresponding points in the underlying metric space whenever the vertices are adjacent in the graph. We consider both general and plane variants of geodesic obstacle representations (in a similar sense to obstacle representations) under any polyhedral distance function in R^d as well as shortest path distances in graphs. Our results generalize and unify the notions of obstacle representations, plane obstacle representations and grid obstacle representations, leading to a number of questions on such representations.
@inproceedings{conf/icalp/BoseCD0MMS18,
author = {Prosenjit Bose and
Paz Carmi and
Vida Dujmovic and
Saeed Mehrabi and
Fabrizio Montecchiani and
Pat Morin and
Lu{\'{\i}}s Fernando Schultz Xavier da Silveira},
title = {Geodesic Obstacle Representation of Graphs},
booktitle = {45th International Colloquium on Automata, Languages, and Programming, {ICALP} 2018, July 9-13, 2018, Prague, Czech Republic},
pages = {23:1--23:13},
year = {2018}
}
Boundary Labeling for Rectangular Diagrams
Abstract: Given a set of n points (sites) inside a rectangle $R$ and $n$ points (label locations or ports) on its boundary, a boundary labeling problem seeks ways of connecting every site to a distinct port while achieving different labeling aesthetics. We examine the scenario when the connecting lines (leaders) are drawn as axis-aligned polylines with few bends, every leader lies strictly inside $R$, no two leaders cross, and the sum of the lengths of all the leaders is minimized. In a $k$-sided boundary labeling problem, where $1\leq k\leq 4$, the label locations are located on the $k$ consecutive sides of $R$.
In this paper we develop an $O(n^3 \log n)$-time algorithm for 2-sided boundary labeling, where the leaders are restricted to have one bend. This improves the previously best known $O(n^8 \log n)$-time algorithm of Kindermann et al. (Algorithmica, 76(1):225-258, 2016). We show the problem is polynomial-time solvable in more general settings such as when the ports are located on more than two sides of $R$, in the presence of obstacles, and even when the objective is to minimize the total number of bends. Our results improve the previous algorithms on boundary labeling with obstacles, as well as provide the first polynomial-time algorithms for minimizing the total leader length and number of bends for 3- and 4-sided boundary labeling. These results settle a number of open questions on the boundary labeling problems (Wolff, Handbook of Graph Drawing, Chapter 23, Table 23.1, 2014).
@inproceedings{conf/swat/BoseCK0M18,
author = {Prosenjit Bose and
Paz Carmi and
J. Mark Keil and
Saeed Mehrabi and
Debajyoti Mondal},
title = {Boundary Labeling for Rectangular Diagrams},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory, {SWAT} 2018, June 18-20, 2018, Malm{\"{o}}, Sweden},
pages = {12:1--12:14},
year = {2018}
}
Approximating Domination on Intersection Graphs of Paths on a Grid
Abstract: A graph $G$ is called $B_k$-$EPG$ (resp., $B_k$-$VPG$), for some constant $k\geq 0$, if it has a string representation on an axis-parallel grid such that each vertex is a path with at most $k$ bends and two vertices are adjacent in $G$ if and only if the corresponding strings share at least one grid edge (resp., the corresponding strings intersect each other). If two adjacent strings of a $B_k$-$VPG$ graph intersect each other exactly once, then the graph is called a one-string $B_k-VPG$ graph.
In this paper, we study the Minimum Dominating Set problem on $B_1$-$EPG$ and $B_1$-$VPG$ graphs. We first give an $O(1)$-approximation algorithm on one-string $B_1$-$VPG$ graphs, providing the first constant-factor approximation algorithm for this problem. Moreover, we show that the Minimum Dominating Set problem is APX-hard on $B_1$-$EPG$ graphs, ruling out the possibility of a PTAS unless P=NP. Finally, to complement our APX-hardness result, we give constant-factor approximation algorithms for the Minimum Dominating Set problem on two non-trivial subclasses of $B_1$-$EPG$ graphs.
Saeed Mehrabi.
In proceedings of the 15th International Workshop on Approximation and Online Algorithms (WAOA 2017), pages 76-89, 2017.
@inproceedings{conf/waoa/Mehrabi17,
author = {Saeed Mehrabi},
title = {Approximating Domination on Intersection Graphs of Paths on a Grid},
booktitle = {Approximation and Online Algorithms - 15th International Workshop, {WAOA} 2017, Vienna, Austria, September 7-8, 2017, Revised Selected
Papers},
pages = {76--89},
year = {2017}
}
Evacuating an Equilateral Triangle in the Face-to-Face Model
Abstract: Consider $k$ robots initially located at the centroid of an equilateral triangle $T$ of sides of length one. The goal of the robots is to evacuate $T$ through an exit at an unknown location on the boundary of $T$. Each robot can move anywhere in $T$ independently of other robots with maximum speed one. The objective is to minimize the evacuation time, which is defined as the time required for all $k$ robots to reach the exit. We consider the face-to-face communication model for the robots: a robot can communicate with another robot only when they meet in $T$.
In this paper, we give upper and lower bounds for the face-to-face evacuation time by $k$ robots. We show that for any $k$, any algorithm for evacuating $k\geq 1$ robots from $T$ requires at least $\sqrt{3}$ time. This bound is asymptotically optimal, as we show that a straightforward strategy of evacuation by $k$ robots gives an upper bound of $\sqrt{3}+3/k$. For $k=3,4,5, 6$, we show significant improvements on the obvious upper bound by giving algorithms with evacuation times of 2.0887, 1.9816, 1.876, and 1.827, respectively. For $k=2$ robots, we give a lower bound of $1+2/\sqrt{3}\approx 2.154$, and an algorithm with upper bound of 2.3367 on the evacuation time.
Huda Chuangpishit,
Saeed Mehrabi,
Lata Narayanan, and
Jaroslav Opatrny.
In proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS 2017), 11:1-11:16. 2017.
@inproceedings{conf/opodis/ChuangpishitMNO17,
author = {Huda Chuangpishit and
Saeed Mehrabi and
Lata Narayanan and
Jaroslav Opatrny},
title = {Evacuating an Equilateral Triangle in the Face-to-Face Model},
booktitle = {21st International Conference on Principles of Distributed Systems, {OPODIS} 2017, Lisbon, Portugal, December 18-20, 2017},
pages = {11:1--11:16},
year = {2017}
}
Grid-Obstacle Representations with Connections to Staircase Guarding
Abstract: In this paper, we study grid-obstacle representations of graphs where we assign grid-points to vertices and define obstacles such that an edge exists if and only if an xy-monotone grid path connects the two endpoints without hitting an obstacle or another vertex. It was previously argued that all planar graphs have a grid-obstacle representation in 2D, and all graphs have a grid-obstacle representation in 3D. In this paper, we show that such constructions are possible with significantly smaller grid-size than previously achieved. Then we study the variant where vertices are not blocking, and show that then grid-obstacle representations exist for bipartite graphs. The latter has applications in so-called staircase guarding of orthogonal polygons; using our grid-obstacle representations, we show that staircase guarding is NP-hard in 2D.
Therese Biedl, and
Saeed Mehrabi.
In proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017), pages 81-87, 2017.
@inproceedings{conf/gd/BiedlM17,
author = {Therese C. Biedl and
Saeed Mehrabi},
title = {Grid-Obstacle Representations with Connections to Staircase Guarding},
booktitle = {Graph Drawing and Network Visualization - 25th International Symposium, {GD} 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers},
pages = {81--87},
year = {2017}
}
On Guarding Orthogonal Polygons with Sliding Cameras
Abstract: A sliding camera inside an orthogonal polygon $P$ is a point guard that travels back and forth along an orthogonal line segment $\gamma$ in $P$. The sliding camera $g$ can see a point $p$ in $P$ if the perpendicular from $p$ onto $\gamma$ 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. On the other hand, we show that the problem is NP-hard on orthogonal polygons with holes even if only horizontal cameras are allowed. Finally, we study art gallery theorems for sliding cameras, thus, give upper and lower bounds in terms of the number of sliding cameras needed relative to the number of vertices $n$.
@inproceedings{conf/walcom/BiedlCL0MV17,
author = {Therese C. Biedl and
Timothy M. Chan and
Stephanie Lee and
Saeed Mehrabi and
Fabrizio Montecchiani and
Hamideh Vosoughpour},
title = {On Guarding Orthogonal Polygons with Sliding Cameras},
booktitle = {{WALCOM:} Algorithms and Computation, 11th International Conference and Workshops, {WALCOM} 2017, Hsinchu, Taiwan, March 29-31, 2017, Proceedings.},
pages = {54--65},
year = {2017}
}
Approximating Weighted Duo-Preservation in Comparative Genomics
Abstract: Motivated by comparative genomics, Chen et al. [9] introduced the Maximum Duo-preservation String Mapping (MDSM) problem in which we are given two strings $s1$ and $s2$ from the same alphabet and the goal is to find a mapping $\pi$ between them so as to maximize the number of duos preserved. A \emph{duo} is any two consecutive characters in a string and it is preserved in the mapping if its two consecutive characters in $s1$ are mapped to same two consecutive characters in $s2$. The MDSM problem is known to be NP-hard and there are approximation algorithms for this problem [3, 5], all of which consider only the ``unweighted'' version of the problem in the sense that a duo from $s1$ is preserved by mapping to any same duo in $s2$ regardless of their positions in the respective strings. However, it is well-desired in comparative genomics to find mappings that consider preserving duos that are ``closer'' to each other under some distance measure [18].
In this paper, we introduce a generalized version of the problem, called the Maximum-Weight Duo-preservation String Mapping (MWDSM) problem, capturing both duos-preservation and duos-distance measures in the sense that mapping a duo from $s1$ to each preserved duo in $s2$ has a weight, indicating the ``closeness'' of the two duos. The objective of the MWDSM problem is to find a mapping so as to maximize the total weight of preserved duos. We give a polynomial-time 6-approximation algorithm for this problem.
Saeed Mehrabi.
In proceedings of the 23rd International Computing and Combinatorics Conference (COCOON 2017), 396-406. 2016.
@inproceedings{conf/cocoon/Mehrabi17,
author = {Saeed Mehrabi},
title = {Approximating Weighted Duo-Preservation in Comparative Genomics},
booktitle = {Computing and Combinatorics - 23rd International Conference, {COCOON} 2017, Hong Kong, China, August 3-5, 2017, Proceedings},
pages = {396--406},
year = {2017}
}
Packing Boundary-Anchored Rectangles
Abstract: In this paper, we study the boundary-anchored rectangle packing problem in which we are given a set $P$ of points on the boundary of an axis-aligned square $Q$. The goal is to find a set of disjoint axis-aligned rectangles in $Q$ such that each rectangle is anchored at some point in $P$, each point in $P$ is used to anchor at most one rectangle, and the total area of the rectangles is maximized. We show how to solve this problem in linear-time in the number of points of $P$, provided that the points of $P$ are given in sorted order along the boundary of $Q$. The solvability of the general version of this problem, in which the points of $P$ can also lie in the interior of $Q$, in polynomial time, is still open.
Therese Biedl,
Ahmad Biniaz,
Anil Maheshwari, and
Saeed Mehrabi.
In proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), pages 138-143., 2017.
Invited to a special issue of Computational Geometry: Theory and Applications.
@inproceedings{conf/cccg/BiedlBMM17,
author = {Therese C. Biedl and
Ahmad Biniaz and
Anil Maheshwari and
Saeed Mehrabi},
title = {Packing Boundary-Anchored Rectangles},
booktitle = {Proceedings of the 29th Canadian Conference on Computational Geometry, {CCCG} 2017, July 26-28, 2017, Carleton University, Ottawa, Ontario, Canada},
pages = {138--143},
year = {2017}
}
On Guarding Orthogonal Polygons with Bounded Treewidth
Abstract: There exist many variants of guarding an orthogonal polygon in an orthogonal fashion: sometimes a guard can see an entire rectangle, or along a staircase, or along a orthogonal path with at most $k$ bends. In this paper, we study all these guarding models in the special case of orthogonal polygons that have bounded treewidth in some sense. Exploiting algorithms for graphs of bounded treewidth, we show that the problem of finding the minimum number of guards in these models becomes linear-time solvable in polygons of bounded treewidth.
Therese Biedl, and
Saeed Mehrabi.
In proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), pages 150-155., 2017.
@inproceedings{conf/cccg/BiedlM17,
author = {Therese C. Biedl and
Saeed Mehrabi},
title = {On Guarding Orthogonal Polygons with Bounded Treewidth},
booktitle = {Proceedings of the 29th Canadian Conference on Computational Geometry, {CCCG} 2017, July 26-28, 2017, Carleton University, Ottawa, Ontario, Canada},
pages = {150--155},
year = {2017}
}
On $r$-Guarding Thin Orthogonal Polygons
Abstract: 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 (and in fact for all orthogonal polygons), but the run-time was $\tilde{O}(n^{17})$. We show here that with a different approach one can find the minimum set of $r$-guards can be found in tree polygons in linear time, 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$.
Therese Biedl, and
Saeed Mehrabi.
In proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), 17:1-17:13. 2016.
@inproceedings{conf/isaac/Biedl016,
author = {Therese C. Biedl and
Saeed Mehrabi},
title = {On r-Guarding Thin Orthogonal Polygons},
booktitle = {27th International Symposium on Algorithms and Computation, {ISAAC} 2016, December 12-14, 2016, Sydney, Australia},
pages = {17:1--17:13},
year = {2016}
}
1-Bend RAC Drawings of 1-Planar Graphs
Abstract: 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 [22]. Also, straight-line RAC drawings always exist for IC-planar graphs [9], 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.
Therese Biedl, and
Saeed Mehrabi.
In proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016), 335-343. 2016.
@inproceedings{conf/gd/DidimoL0M16,
author = {Walter Didimo and
Giuseppe Liotta and
Saeed Mehrabi and
Fabrizio Montecchiani},
title = {1-Bend {RAC} Drawings of 1-Planar Graphs},
booktitle = {Graph Drawing and Network Visualization - 24th International Symposium, {GD} 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers},
pages = {335--343},
year = {2016}
}
Polygon Simplification by Minimizing Convex Corners
Abstract: Let $P$ be a polygon with $r>0$ reflex vertices and possibly with holes. A subsuming polygon of $P$ is a polygon $P'$ such that $P\subseteq P'$, each connected component $R'$ of $P'$ subsumes a distinct component $R$ of $P$, i.e., $R\subseteq R'$, and the reflex corners of $R$ coincide with the reflex corners of $R'$. A subsuming chain of $P'$ is a minimal path on the boundary of $P'$ whose two end edges coincide with two edges of $P$. Aichholzer et al. proved that every polygon $P$ has a subsuming polygon with $O(r)$ vertices. Let $\mathcal{A}_e(P)$ (resp., $\mathcal{A}_v(P)$) be the arrangement of lines determined by the edges (resp., pairs of vertices) of $P$. Aichholzer et al. observed that a challenge of computing an optimal subsuming polygon $P'_{min}$, i.e., a subsuming polygon with minimum number of convex vertices, is that it may not always lie on $\mathcal{A}_e(P)$. We prove that in some settings, one can find an optimal subsuming polygon for a given simple polygon in polynomial time, i.e., when $\mathcal{A}_e(P'_{min})=\mathcal{A}_e(P)$ and the subsuming chains are of constant length. In contrast, we prove the problem to be NP-hard for polygons with holes, even if there exists some $P'_{min}$ with $\mathcal{A}_e(P'_{min})=\mathcal{A}_e(P)$ and subsuming chains are of length three. Both results extend to the scenario when $\mathcal{A}_v(P'_{min})=\mathcal{A}_v(P)$.
Yeganeh Bahoo,
Stephane Durocher,
J. Mark Keil, Saeed Mehrabi,
Sahar Mehrpour, and
Debajyoti Mondal.
In proceedings of the 22nd International Computing and Combinatorics Conference (COCOON 2016), 547-559. 2016.
@inproceedings{conf/cocoon/BahooDK0MM16,
author = {Yeganeh Bahoo and
Stephane Durocher and
J. Mark Keil and
Saeed Mehrabi and
Sahar Mehrpour and
Debajyoti Mondal},
title = {Polygon Simplification by Minimizing Convex Corners},
booktitle = {Computing and Combinatorics - 22nd International Conference, {COCOON} 2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings},
pages = {547--559},
year = {2016}
}
Geometric Unique Set Cover on Unit Disks and Unit Squares
Abstract: 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).
Saeed Mehrabi.
In proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 195-200, 2016.
@inproceedings{conf/cccg/Mehrabi16,
author = {Saeed Mehrabi},
title = {Geometric Unique Set Cover on Unit Disks and Unit Squares},
booktitle = {Proceedings of the 28th Canadian Conference on Computational Geometry,
{CCCG} 2016, August 3-5, 2016, Simon Fraser University, Vancouver,
British Columbia, Canada},
pages = {195--200},
year = {2016}
}
Rectangle-of-influence Triangulations
Abstract: A rectangle-of-influence (RI) drawing is a straight-line drawing where for every edge $(u,v)$ the minimum axis-aligned rectangle containing $u$ and $v$ contains no other points. In this paper, we show how to create RI-triangulations (i.e., triangulations that are RI-drawings) for any point set. Moreover, by using the $L^\infty$-Delaunay-triangulations, we show that we can flip from any RI-triangulation to any other while maintaining RI-triangulations.
Therese Biedl,
Anna Lubiw,
Saeed Mehrabi, and
Sander Verdonschot.
In proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 237-243, 2016.
@inproceedings{conf/cccg/BiedlLMV16,
author = {Therese C. Biedl and
Anna Lubiw and
Saeed Mehrabi and
Sander Verdonschot},
title = {Rectangle-of-influence triangulations},
booktitle = {Proceedings of the 28th Canadian Conference on Computational Geometry, {CCCG} 2016, August 3-5, 2016, Simon Fraser University, Vancouver, British Columbia, Canada},
pages = {237--243},
year = {2016}
}
Sliding $k$-Transmitters: Hardness and Approximation
Abstract: 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.
Therese Biedl,
Saeed Mehrabi, and
Ziting Yu.
In proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 63--68, 2016.
@inproceedings{conf/cccg/Biedl0Y16,
author = {Therese C. Biedl and
Saeed Mehrabi and
Ziting Yu},
title = {Sliding k-Transmitters: Hardness and Approximation},
booktitle = {Proceedings of the 28th Canadian Conference on Computational Geometry, {CCCG} 2016, August 3-5, 2016, Simon Fraser University, Vancouver, British Columbia, Canada},
pages = {63--68},
year = {2016}
}
Guarding Orthogonal Terrains
Abstract: A 1.5-dimensional terrain $T$ with $n$ vertices is an $x$-monotone polygonal chain in the plane. A point guard $p$ on $T$ guards a point $q$ of $T$ if the line segment connecting $p$ to $q$ lies on or above $T$; $p$ is a vertex guard if it is a vertex of $T$. In the Optimal Terrain Guarding (OTG) problem on $T$, the objective is to guard the vertices of $T$ by the minimum number of vertex guards. King and Krohn [9] showed that the OTG problem is NP-hard on arbitrary terrains, and Gibson et al. [6] gave a PTAS for this problem. In this paper, we introduce directed visibility in which the visibility is directed only at adjacent vertices. We give an $O(n)$-time algorithm that solves the OTG problem exactly on orthogonal terrains under directed visibility.
Stephane Durocher,
Pak Ching Li, and
Saeed Mehrabi.
In proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), , 2015.
@inproceedings{conf/cccg/DurocherLM15,
author = {Stephane Durocher and
Pak Ching Li and
Saeed Mehrabi},
title = {Guarding Orthogonal Terrains},
booktitle = {Proceedings of the 27th Canadian Conference on Computational Geometry, {CCCG} 2015, Kingston, Ontario, Canada, August 10-12, 2015},
year = {2015}
}
Guarding Monotone Art Galleries with Sliding Cameras in Linear Time
Abstract: A sliding camera in an orthogonal polygon $P$ is a point guard $g$ that travels back and forth along an orthogonal line segment $s$ inside $P$. A point $p$ in $P$ is guarded by $g$ if and only if there exists a point $q$ on $s$ such that line segment $pq$ is normal to $s$ and contained in $P$. In the minimum sliding cameras (MSC) problem, the objective is to guard $P$ with the minimum number of sliding cameras. We give a linear-time dynamic programming algorithm for the MSC problem on $x$-monotone orthogonal polygons, improving the 2-approximation algorithm of Katz and Morgenstern (2011). More generally, our algorithm can be used to solve the MSC problem in linear time on simple orthogonal polygons $P$ for which the dual graph induced by the vertical decomposition of $P$ is a path. Our results provide the first polynomial-time exact algorithms for the MSC problem on a non-trivial subclass of orthogonal polygons.
Mark de Berg,
Stephane Durocher, and
Saeed Mehrabi.
In proceedings of the 8th International Conference on Combinatorial Optimization and Applications (COCOA 2014), pages 113-125, 2014.
@inproceedings{conf/cocoa/BergD014,
author = {Mark de Berg and
Stephane Durocher and
Saeed Mehrabi},
title = {Guarding Monotone Art Galleries with Sliding Cameras in Linear Time},
booktitle = {Combinatorial Optimization and Applications - 8th International Conference, {COCOA} 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings},
pages = {113--125},
year = {2014}
}
A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
Abstract: 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.
@inproceedings{conf/latin/DurocherFFM014,
author = {Stephane Durocher and
Omrit Filtser and
Robert Fraser and
Ali D. Mehrabi and
Saeed Mehrabi},
title = {A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries
with Sliding Cameras},
booktitle = {{LATIN} 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings},
pages = {294--305},
year = {2014}
}
Drawing HV-Restricted Planar Graphs
Abstract: A strict orthogonal drawing of a graph $G=(V, E)$ in $\mathbb{R}^2$ is a drawing of $G$ such that each vertex is mapped to a distinct point and each edge is mapped to a horizontal or vertical line segment. A graph $G$ is HV-restricted if each of its edges is assigned a horizontal or vertical orientation. A strict orthogonal drawing of an HV-restricted graph $G$ is good if it is planar and respects the edge orientations of $G$. In this paper we give a polynomial-time algorithm to check whether a given HV-restricted plane graph (i.e., a planar graph with a fixed combinatorial embedding) admits a good orthogonal drawing preserving the input embedding, which settles an open question posed by Manuch, Patterson, Poon and Thachuk (GD 2010). We then examine HV-restricted planar graphs (i.e., when the embedding is not fixed). Here we completely characterize the 2-connected maximum-degree-three HV-restricted outerplanar graphs that admit good orthogonal drawings.
@inproceedings{conf/latin/DurocherF0M14,
author = {Stephane Durocher and
Stefan Felsner and
Saeed Mehrabi and
Debajyoti Mondal},
title = {Drawing HV-Restricted Planar Graphs},
booktitle = {{LATIN} 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings},
pages = {156--167},
year = {2014}
}
A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
Abstract: A sliding camera travelling along a line segment $s$ in a polygon $P$ can see a point $p$ in $P$ if and only if $p$ lies on a line segment contained in $P$ that intersects $s$ at a right angle. The objective of the minimum sliding cameras (MSC) problem is to guard $P$ with the fewest sliding cameras possible, each of which is a horizontal or vertical line segment. In this paper, we give an $O(n^3)$-time 3-approximation algorithm for the MSC problem on any simple orthogonal polygon with n vertices. Our algorithm involves establishing a connection between the MSC problem and the problem of guarding simple grids with periscope guards.
Stephane Durocher, and
Saeed Mehrabi.
In proceedings of the 25th International Workshop on Combinatorial Algorithms (IWOCA 2014), pages 140-152, 2014.
@inproceedings{conf/iwoca/Durocher014,
author = {Stephane Durocher and
Saeed Mehrabi},
title = {A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries
with Sliding Cameras},
booktitle = {Combinatorial Algorithms - 25th International Workshop, {IWOCA} 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers},
pages = {140--152},
year = {2014}
}
Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic and Hardness Results
Abstract: Let $P$ be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment $s\subseteq P$ as its 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 contained in $P$. In the 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 in $S$) while in the 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 posed by Katz and Morgenstern [9]. Next we show that the minimum-cardinality sliding cameras problem is NP-hard when $P$ is allowed to have holes, which partially answers another question posed by Katz and Morgenstern [9].
Stephane Durocher, and
Saeed Mehrabi.
In proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), pages 314-324, 2013.
@inproceedings{conf/mfcs/Durocher013,
author = {Stephane Durocher and
Saeed Mehrabi},
title = {Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic
and Hardness Results},
booktitle = {Mathematical Foundations of Computer Science 2013 - 38th International Symposium, {MFCS} 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings},
pages = {314--324},
year = {2013}
}
On $k$-Enclosing Objects in a Coloured Point Set
Abstract: We introduce the exact coloured $k$-enclosing object problem: given a set $P$ of $n$ points in $\mathbb{R}^2$, each of which has an associated colour in $\{1,\dots, t\}$, and a vector $c=(c_1,\dots, c_t)$, where $c_i\in \mathbb{Z}^+$ for each $1\leq i\leq t$, find a region that contains exactly $c_i$ points of $P$ of colour $i$ for each $i$. We examine the problems of finding exact coloured $k$-enclosing axis-aligned rectangles, squares, discs, and two-sided dominating regions in a $t$-coloured point set.
@inproceedings{conf/cccg/BarbaDFH0MMSW13,
author = {Luis Barba and
Stephane Durocher and
Robert Fraser and
Ferran Hurtado and
Saeed Mehrabi and
Debajyoti Mondal and
Jason Morrison and
Matthew Skala and
Mohammad Abdul Wahid},
title = {On k-Enclosing Objects in a Coloured Point Set},
booktitle = {Proceedings of the 25th Canadian Conference on Computational Geometry, {CCCG} 2013, Waterloo, Ontario, Canada, August 8-10, 2013},
year = {2013}
}
Computing Partitions of Rectilinear Polygons with Minimum Stabbing Number
Abstract: The stabbing number of a partition of a rectilinear polygon $P$ into rectangles is the maximum number of rectangles stabbed by any axis-parallel line segment contained in $P$. We consider the problem of finding a rectangular partition with minimum stabbing number for a given rectilinear polygon $P$. First, we impose a conforming constraint on partitions: every vertex of every rectangle in the partition must lie on the polygon's boundary. We show that finding a conforming rectangular partition of minimum stabbing number is NP-hard for rectilinear polygons with holes. We present a rounding method based on a linear programming relaxation resulting in a polynomial-time 2-approximation algorithm. We give an $O(n \log n)$-time algorithm to solve the problem exactly when $P$ is a histogram (some edge in $P$ can see every point in $P$) with $n$ vertices. Next we relax the conforming constraint and show how to extend the first linear program to achieve a polynomial-time 2-approximation algorithm for the general problem, improving the approximation factor achieved by Abam, Aronov, de Berg, and Khosravi (ACM SoCG 2011).
Stephane Durocher, and
Saeed Mehrabi.
In proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON 2012), pages 228-239, 2012.
@inproceedings{conf/cocoon/DurocherM12,
author = {Stephane Durocher and
Saeed Mehrabi},
title = {Computing Partitions of Rectilinear Polygons with Minimum Stabbing
Number},
booktitle = {Computing and Combinatorics - 18th Annual International Conference, {COCOON} 2012, Sydney, Australia, August 20-22, 2012. Proceedings},
pages = {228--239},
year = {2012}
}
The Cover Contact Graph of Discs Touching a Line
Abstract: We answer a question of Atienza et al. [4] by showing that the circular $CCG^+$ problem is NP-complete. If we cover a set of objects on the plane with discs whose interiors are pairwise disjoint, then we can form a cover contact graph (CCG) that records which of the covering discs touch at their boundaries. When the input objects are themselves discs, and both input and covering discs are constrained to be touching and above the $x$-axis, then the circular $CCG^+$ problem is to decide the existence of a covering with a connected CCG. We also
define an approximate version of this problem by allowing a small overlap between covering discs, and give an algorithm that in polynomial time finds an approximate solution for any yes-instance of the exact problem.
@inproceedings{conf/cccg/Durocher0SW12,
author = {Stephane Durocher and
Saeed Mehrabi and
Matthew Skala and
Mohammad Abdul Wahid},
title = {The Cover Contact Graph of Discs Touching a Line},
booktitle = {Proceedings of the 24th Canadian Conference on Computational Geometry, {CCCG} 2012, Charlottetown, Prince Edward Island, Canada, August 8-10, 2012},
pages = {59--64},
year = {2012}
}
Realizing Site Permutations
Abstract: Given $n$ fixed sites on the plane, there are several ways to determine a permutation of the sites as a function of a unit vector $u$ or a vantage point $v$. Given such a scheme and a permutation $\pi$, we can ask whether there is any unit vector or vantage point for which the permutation is $\pi$. We give linear-time algorithms for this realization problem under three schemes for determining permutations: sweeping a line across the sites in a direction $u$; expanding a circle starting from a vantage point $v$; and sweeping a ray from $v$ to give a cyclic permutation.
@inproceedings{conf/cccg/DurocherMMS11,
author = {Stephane Durocher and
Saeed Mehrabi and
Debajyoti Mondal and
Matthew Skala},
title = {Realizing Site Permutations},
booktitle = {Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Toronto, Ontario, Canada, August 10-12, 2011},
year = {2011}
}
Geometric Optimization Problems on Orthogonal Polygons: Hardness Results and Approximation Algorithms
Abstract:
In this thesis, we design and develop new approximation algorithms and complexity results for three guarding and partitioning problems on orthogonal polygons; namely, guarding orthogonal polygons using sliding cameras, partitioning orthogonal polygons so as to minimize the stabbing number and guarding orthogonal terrains using vertex guards.
We first study a variant of the well-known art gallery problem in which sliding cameras are used to guard the polygon. We consider two versions of this problem: the Minimum-Cardinality Sliding Cameras (MCSC) problem in which we want to guard $P$ with the minimum number of sliding cameras, and the Minimum-Length Sliding Cameras (MLSC) problem in which the goal is to compute a set $S$ of sliding cameras for guarding $P$ so as to minimize the total length of trajectories along which the cameras in $S$ travel. We answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP-complete when $P$ is allowed to have holes, and (iii) an $O(n)$-time exact algorithm for the MCSC problem on monotone polygons.
We then study a conforming variant of the problem of computing a partition of an orthogonal polygon $P$ into rectangles whose stabbing number is minimum over all such partitions of $P$. The stabbing number of such a partition is the maximum number of rectangles intersected by any orthogonal line segment inside the polygon. In this thesis, we first give an $O(n \log n)$-time algorithm that solves this problem exactly on histograms. We then show that the problem is NP-hard for orthogonal polygons with holes, providing the first hardness result for this problem. To complement the NP-hardness result, we give a 2-approximation algorithm for the problem on both polygons with and without holes.
Finally, we study a variant of the terrain guarding problem on orthogonal terrains in which the objective is to guard the vertices of an orthogonal terrain with the minimum number of vertex guards. We give a linear-time algorithm for this problem under a directed visibility constraint.
@phdthesis{saeedPhdThesis,
author={Saeed Mehrabi},
title={Geometric Optimization Problems on Orthogonal Polygons: Hardness Results and Approximation Algorithms},
type={PhD thesis},
school={University of Manitoba},
year={2015}
}
Online Problems in Facility Location
Abstract: We introduce two online models for the vertex $k$-center and the vertex $k$-median problems. Clients (i.e., graph vertices) and their corresponding links (i.e., graph edges) are revealed sequentially, determining the topology of a graph over time. Clients are revealed by an adversary to an online algorithm that selects existing graph vertices on which to open facilities; once open, a facility cannot be removed or relocated. We define two models: an online algorithm may be restricted to open a facility only at the location of the most recent client or at the location of any existing client. We examine these models on three classes of graphs under two types of adversaries. We establish lower bounds on the respective competitive ratios attainable by any online algorithm for each combination of model, adversary, and graph class. Finally, we describe algorithms whose competitive ratios provide corresponding upper bounds on the best competitive ratios achievable.