The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform

Saeed Mehrabi - One of the best experts on this subject based on the ideXlab platform.

  • guarding orthogonal Art Galleries with sliding k transmitters hardness and approximation
    Algorithmica, 2019
    Co-Authors: Therese C Biedl, Saeed Mehrabi, Timothy M Chan, Stephanie Lee, Fabrizio Montecchiani, Hamideh Vosoughpour
    Abstract:

    A sliding k-transmitter inside an orthogonal polygon P, for a fixed $$k\ge 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 ( $${\hbox {ST}}_k$$ ) 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 $${\hbox {ST}}_k$$ problem on P for any fixed $$k\ge 0$$ . Moreover, we show that the $${\hbox {ST}}_0$$ 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.

  • guarding orthogonal Art Galleries with sliding cameras
    Computational Geometry: Theory and Applications, 2017
    Co-Authors: Stephane Durocher, Omrit Filtser, Robert Fraser, Ali D Mehrabi, Saeed Mehrabi
    Abstract:

    Abstract Let P be an orthogonal polygon with n vertices. A sliding camera travels back and forth along an orthogonal line segment s ⊆ P corresponding to its trajectory. The camera sees a point p ∈ P if there is a point q ∈ s such that p q ‾ 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).

  • Guarding monotone Art Galleries with sliding cameras in linear time
    Journal of Discrete Algorithms, 2017
    Co-Authors: Mark De Berg, Stephane Durocher, Saeed Mehrabi
    Abstract:

    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.

  • guarding monotone Art Galleries with sliding cameras in linear time
    Conference on Combinatorial Optimization and Applications, 2014
    Co-Authors: Mark De Berg, Stephane Durocher, Saeed Mehrabi
    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.

  • a 3 approximation algorithm for guarding orthogonal Art Galleries with sliding cameras
    International Workshop on Combinatorial Algorithms, 2014
    Co-Authors: Stephane Durocher, Saeed Mehrabi
    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 - One of the best experts on this subject based on the ideXlab platform.

  • guarding orthogonal Art Galleries with sliding cameras
    Computational Geometry: Theory and Applications, 2017
    Co-Authors: Stephane Durocher, Omrit Filtser, Robert Fraser, Ali D Mehrabi, Saeed Mehrabi
    Abstract:

    Abstract Let P be an orthogonal polygon with n vertices. A sliding camera travels back and forth along an orthogonal line segment s ⊆ P corresponding to its trajectory. The camera sees a point p ∈ P if there is a point q ∈ s such that p q ‾ 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).

  • Guarding monotone Art Galleries with sliding cameras in linear time
    Journal of Discrete Algorithms, 2017
    Co-Authors: Mark De Berg, Stephane Durocher, Saeed Mehrabi
    Abstract:

    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.

  • guarding monotone Art Galleries with sliding cameras in linear time
    Conference on Combinatorial Optimization and Applications, 2014
    Co-Authors: Mark De Berg, Stephane Durocher, Saeed Mehrabi
    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.

  • a 3 approximation algorithm for guarding orthogonal Art Galleries with sliding cameras
    International Workshop on Combinatorial Algorithms, 2014
    Co-Authors: Stephane Durocher, Saeed Mehrabi
    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.

  • guarding orthogonal Art Galleries using sliding cameras algorithmic and hardness results
    Mathematical Foundations of Computer Science, 2013
    Co-Authors: Stephane Durocher, Saeed Mehrabi
    Abstract:

    Let P be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment s ⊆ P as its trajectory. The camera can see a point p ∈ P if there exists a point q ∈ 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.

Max Willert - One of the best experts on this subject based on the ideXlab platform.

  • tight bounds for conflict free chromatic guarding of orthogonal Art Galleries
    Computational Geometry: Theory and Applications, 2018
    Co-Authors: Frank Hoffmann, Klaus Kriegel, Subhash Suri, Kevin Verbeek, Max Willert
    Abstract:

    Abstract The chromatic Art gallery problem asks for the minimum number of “colors” t so that a collection of point guards, each assigned one of the t colors, can see the entire polygon subject to some conditions on the colors visible to each point. In this paper, we explore this problem for orthogonal polygons using orthogonal visibility—two points p and q are mutually visible if the smallest axis-aligned rectangle containing them lies within the polygon. Our main result establishes that for a conflict-free guarding of an orthogonal n-gon, in which at least one of the colors seen by every point is unique, the number of colors is in the worst case Θ ( log ⁡ log ⁡ n ) . By contrast, the best known upper bound for orthogonal polygons under standard (non-orthogonal) visibility is O ( log ⁡ n ) colors. We also show that the number of colors needed for strong guarding of simple orthogonal polygons, where all the colors visible to a point are unique, is, again in the worst case, Θ ( log ⁡ n ) . Finally, our techniques also help us establish the first non-trivial lower bound of Ω ( log ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ) for conflict-free guarding under standard visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau.

  • tight bounds for conflict free chromatic guarding of orthogonal Art Galleries
    Symposium on Computational Geometry, 2015
    Co-Authors: Frank Hoffmann, Klaus Kriegel, Subhash Suri, Kevin Verbeek, Max Willert
    Abstract:

    The chromatic Art gallery problem asks for the minimum number of "colors" t so that a collection of point guards, each assigned one of the t colors, can see the entire polygon subject to some conditions on the colors visible to each point. In this paper, we explore this problem for orthogonal polygons using orthogonal visibility - two points p and q are mutually visible if the smallest axis-aligned rectangle containing them lies within the polygon. Our main result establishes that for a conflict-free guarding of an orthogonal n-gon, in which at least one of the colors seen by every point is unique, the number of colors is Theta(loglog n). By contrast, the best upper bound for orthogonal polygons under standard (non-orthogonal) visibility is O(log n) colors. We also show that the number of colors needed for strong guarding of simple orthogonal polygons, where all the colors visible to a point are unique, is Theta(log n). Finally, our techniques also help us establish the first non-trivial lower bound of Omega(loglog n / logloglog n) for conflict-free guarding under standard visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau.

Mark De Berg - One of the best experts on this subject based on the ideXlab platform.

  • Guarding monotone Art Galleries with sliding cameras in linear time
    Journal of Discrete Algorithms, 2017
    Co-Authors: Mark De Berg, Stephane Durocher, Saeed Mehrabi
    Abstract:

    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.

  • guarding monotone Art Galleries with sliding cameras in linear time
    Conference on Combinatorial Optimization and Applications, 2014
    Co-Authors: Mark De Berg, Stephane Durocher, Saeed Mehrabi
    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.

Thomas C Shermer - One of the best experts on this subject based on the ideXlab platform.

  • recent results in Art Galleries geometry
    Proceedings of the IEEE, 1992
    Co-Authors: Thomas C Shermer
    Abstract:

    Two points in a polygon are called if the straight line between them lies entirely inside the polygon. The Art gallery problem for a polygon P is to find a minimum set of points G in P such that every point in P is visible from some point of G. The author provides an introduction to Art gallery theorems and surveys the recent results of the field. The emphasis is on the results rather than the techniques. Several new problems that have the same geometric flavor as Art gallery problems are also examined. >

  • recent results in Art Galleries
    Proceedings of the IEEE, 1992
    Co-Authors: Thomas C Shermer
    Abstract:

    Two points in a polygon are called visible if the straight line segment between them lies entirely inside the polygon. The Art gallery problem for a polygon P is to find a minimum set of points G in P such that every point of P is visible from some point of G. This problem has been shown to be NP-hard by Lee and Lin [71]. However, Chvatal showed that the number of points of G will never exceed [n/3] for a simple polygon of n sides [21]. This latter result is referred to as the Art gallery theorem