The Experts below are selected from a list of 3870 Experts worldwide ranked by ideXlab platform
Amirhossein Mozafari - One of the best experts on this subject based on the ideXlab platform.
-
transmitting particles in a Polygonal Domain by repulsion
Conference on Combinatorial Optimization and Applications, 2018Co-Authors: Amirhossein Mozafari, Thomas C ShermerAbstract:In this paper, we introduce the problem of transmitting particles to a target point by the effect of a repulsion actuator (RA). In this problem, we are given a Polygonal Domain P and a target point t inside it. Also, there is a particle at each point of P. The question is which particles can get to the target point t by activating a RA in P. We present the first polynomial time algorithm to solve this problem.
-
COCOA - Transmitting Particles in a Polygonal Domain by Repulsion.
Combinatorial Optimization and Applications, 2018Co-Authors: Amirhossein Mozafari, Thomas C ShermerAbstract:In this paper, we introduce the problem of transmitting particles to a target point by the effect of a repulsion actuator (RA). In this problem, we are given a Polygonal Domain P and a target point t inside it. Also, there is a particle at each point of P. The question is which particles can get to the target point t by activating a RA in P. We present the first polynomial time algorithm to solve this problem.
-
touring convex polygons in Polygonal Domain fences
Conference on Combinatorial Optimization and Applications, 2017Co-Authors: Arash Ahadi, Amirhossein Mozafari, Alireza ZareiAbstract:In the touring polygons problem (TPP), for a given sequence \((s=P_0,P_1,\dots ,P_k,t=P_{k+1})\) of polygons in the plane, where s and t are two points, the goal is to find a shortest path that starts from s, visits each of the polygons in order and ends at t. In the constrained version of TPP, there is another sequence \((F_{0},\dots ,F_{k})\) of polygons called fences, and the portion of the path from \(P_i\) to \(P_{i+1}\) must lie inside the fence \(F_{i}\). TPP is NP-hard for disjoint non-convex polygons, while TPP and constrained TPP are polynomially solvable when the polygons are convex and the fences are simple polygons. In this work, we present the first polynomial time algorithm for solving constrained TPP when the fences are Polygonal Domains (polygons with holes). Since, the safari problem is a special case of TPP, our algorithm can be used for solving safari problem inside polygons with holes.
-
COCOA (2) - Touring Convex Polygons in Polygonal Domain Fences
Combinatorial Optimization and Applications, 2017Co-Authors: Arash Ahadi, Amirhossein Mozafari, Alireza ZareiAbstract:In the touring polygons problem (TPP), for a given sequence \((s=P_0,P_1,\dots ,P_k,t=P_{k+1})\) of polygons in the plane, where s and t are two points, the goal is to find a shortest path that starts from s, visits each of the polygons in order and ends at t. In the constrained version of TPP, there is another sequence \((F_{0},\dots ,F_{k})\) of polygons called fences, and the portion of the path from \(P_i\) to \(P_{i+1}\) must lie inside the fence \(F_{i}\). TPP is NP-hard for disjoint non-convex polygons, while TPP and constrained TPP are polynomially solvable when the polygons are convex and the fences are simple polygons. In this work, we present the first polynomial time algorithm for solving constrained TPP when the fences are Polygonal Domains (polygons with holes). Since, the safari problem is a special case of TPP, our algorithm can be used for solving safari problem inside polygons with holes.
-
touring a sequence of line segments in Polygonal Domain fences
Canadian Conference on Computational Geometry, 2015Co-Authors: Amirhossein Mozafari, Alireza ZareiAbstract:In this paper, we consider the problem of touring a sequence of line segments in presence of Polygonal Domain fences. In this problem there is a sequence S = (s = S0;:::;Sk;Sk+1 = t) in which s and t are respectively start and target points and S1;:::;Sk are line segments in the plane. Also, we are given a sequence F = (F0;:::;Fk) of planar Polygonal Domains called fences such that Si[Si+1 Fi. The goal is to obtain a shortest path from s to t which visits in order each of the segments in S in such a way that the portion of the path from Si to Si+1 lies in Fi. In 2003, Dror et. al. proposed a polynomial time algorithm for this problem when the fences are simple polygons. Here, we propose an ecient polynomial time algorithm for this problem when the fences are Polygonal Domains (simple polygons with some Polygonal holes inside).
Sang Won Bae - One of the best experts on this subject based on the ideXlab platform.
-
Computing the geodesic centers of a Polygonal Domain
Computational Geometry, 2019Co-Authors: Sang Won Bae, Matias Korman, Yoshio OkamotoAbstract:Abstract We present an algorithm that computes the geodesic center of a given Polygonal Domain. The running time of our algorithm is O ( n 12 + ϵ ) for any ϵ > 0 , where n is the number of corners of the input Polygonal Domain. Prior to our work, only the very special case where a simple polygon is given as input has been intensively studied in the 1980s, and an O ( n log n ) -time algorithm is known by Pollack et al. Our algorithm is the first one that can handle general Polygonal Domains having one or more Polygonal holes.
-
Computing the $$L_1$$L1 Geodesic Diameter and Center of a Polygonal Domain
Discrete & Computational Geometry, 2016Co-Authors: Sang Won Bae, Matias Korman, Yoshio Okamoto, Valentin Polishchuk, Joseph S. B. Mitchell, Haitao WangAbstract:For a Polygonal Domain with h holes and a total of n vertices, we present algorithms that compute the $$L_1$$L1 geodesic diameter in $$O(n^2+h^4)$$O(n2+h4) time and the $$L_1$$L1 geodesic center in $$O((n^4+n^2 h^4)\alpha (n))$$O((n4+n2h4)ź(n)) time, respectively, where $$\alpha (\cdot )$$ź(·) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in $$O(n^{7.73})$$O(n7.73) or $$O(n^7(h+\log n))$$O(n7(h+logn)) time, and compute the geodesic center in $$O(n^{11}\log n)$$O(n11logn) time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on $$L_1$$L1 shortest paths in Polygonal Domains.
-
computing the l1 geodesic diameter and center of a Polygonal Domain
Symposium on Theoretical Aspects of Computer Science, 2016Co-Authors: Sang Won Bae, Matias Korman, Yoshio Okamoto, Valentin Polishchuk, Joseph S. B. Mitchell, Haitao WangAbstract:For a Polygonal Domain with h holes and a total of n vertices, we present algorithms that compute the L_1 geodesic diameter in O(n^2+h^4) time and the L_1 geodesic center in O((n^4+n^2 h^4)*alpha(n)) time, where alpha(.) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n^{7.73}) or O(n^7(h+log(n))) time, and compute the geodesic center in O(n^{12+epsilon}) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L_1 shortest paths in Polygonal Domains.
-
STACS - Computing the L1 Geodesic Diameter and Center of a Polygonal Domain
2016Co-Authors: Sang Won Bae, Matias Korman, Yoshio Okamoto, Valentin Polishchuk, Joseph S. B. Mitchell, Haitao WangAbstract:For a Polygonal Domain with h holes and a total of n vertices, we present algorithms that compute the L_1 geodesic diameter in O(n^2+h^4) time and the L_1 geodesic center in O((n^4+n^2 h^4)*alpha(n)) time, where alpha(.) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n^{7.73}) or O(n^7(h+log(n))) time, and compute the geodesic center in O(n^{12+epsilon}) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L_1 shortest paths in Polygonal Domains.
-
Computing the $L_1$ Geodesic Diameter and Center of a Polygonal Domain
arXiv: Computational Geometry, 2015Co-Authors: Sang Won Bae, Matias Korman, Yoshio Okamoto, Valentin Polishchuk, Joseph S. B. Mitchell, Haitao WangAbstract:For a Polygonal Domain with $h$ holes and a total of $n$ vertices, we present algorithms that compute the $L_1$ geodesic diameter in $O(n^2+h^4)$ time and the $L_1$ geodesic center in $O((n^4+n^2 h^4)\alpha(n))$ time, respectively, where $\alpha(\cdot)$ denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in $O(n^{7.73})$ or $O(n^7(h+\log n))$ time, and compute the geodesic center in $O(n^{11}\log n)$ time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on $L_1$ shortest paths in Polygonal Domains.
Thomas C Shermer - One of the best experts on this subject based on the ideXlab platform.
-
transmitting particles in a Polygonal Domain by repulsion
Conference on Combinatorial Optimization and Applications, 2018Co-Authors: Amirhossein Mozafari, Thomas C ShermerAbstract:In this paper, we introduce the problem of transmitting particles to a target point by the effect of a repulsion actuator (RA). In this problem, we are given a Polygonal Domain P and a target point t inside it. Also, there is a particle at each point of P. The question is which particles can get to the target point t by activating a RA in P. We present the first polynomial time algorithm to solve this problem.
-
COCOA - Transmitting Particles in a Polygonal Domain by Repulsion.
Combinatorial Optimization and Applications, 2018Co-Authors: Amirhossein Mozafari, Thomas C ShermerAbstract:In this paper, we introduce the problem of transmitting particles to a target point by the effect of a repulsion actuator (RA). In this problem, we are given a Polygonal Domain P and a target point t inside it. Also, there is a particle at each point of P. The question is which particles can get to the target point t by activating a RA in P. We present the first polynomial time algorithm to solve this problem.
Yoshio Okamoto - One of the best experts on this subject based on the ideXlab platform.
-
Rectilinear link diameter and radius in a rectilinear Polygonal Domain
Computational Geometry, 2021Co-Authors: Elena Arseneva, Aleksandar Markovic, Man-kwun Chiu, Matias Korman, Yoshio Okamoto, Aurélien Ooms, André Van Renssen, Marcel RoeloffzenAbstract:Abstract We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear Polygonal Domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the Domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O ( min ( n ω , n 2 + n h log h + χ 2 ) ) time, where ω 2.373 denotes the matrix multiplication exponent and χ ∈ Ω ( n ) ∩ O ( n 2 ) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O ( n 2 log n ) time.
-
Computing the geodesic centers of a Polygonal Domain
Computational Geometry, 2019Co-Authors: Sang Won Bae, Matias Korman, Yoshio OkamotoAbstract:Abstract We present an algorithm that computes the geodesic center of a given Polygonal Domain. The running time of our algorithm is O ( n 12 + ϵ ) for any ϵ > 0 , where n is the number of corners of the input Polygonal Domain. Prior to our work, only the very special case where a simple polygon is given as input has been intensively studied in the 1980s, and an O ( n log n ) -time algorithm is known by Pollack et al. Our algorithm is the first one that can handle general Polygonal Domains having one or more Polygonal holes.
-
Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain
arXiv: Computational Geometry, 2017Co-Authors: Man-kwun Chiu, Aleksandar Markovic, Elena Khramtcova, Matias Korman, Yoshio Okamoto, Aurélien Ooms, André Van Renssen, Marcel RoeloffzenAbstract:We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear Polygonal Domain of $n$ vertices and $h$ holes. We introduce a \emph{graph of oriented distances} to encode the distance between pairs of points of the Domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in $\min \{\,O(n^\omega), O(n^2 + nh \log h + \chi^2)\,\}$ time, where $\omega
-
rectilinear link diameter and radius in a rectilinear Polygonal Domain
arXiv: Computational Geometry, 2017Co-Authors: Man-kwun Chiu, Aleksandar Markovic, Elena Khramtcova, Matias Korman, Yoshio Okamoto, Aurélien Ooms, André Van Renssen, Marcel RoeloffzenAbstract:We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear Polygonal Domain of $n$ vertices and $h$ holes. We introduce a \emph{graph of oriented distances} to encode the distance between pairs of points of the Domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in $\min \{\,O(n^\omega), O(n^2 + nh \log h + \chi^2)\,\}$ time, where $\omega<2.373$ denotes the matrix multiplication exponent and $\chi\in \Omega(n)\cap O(n^2)$ is the number of edges of the graph of oriented distances. We also provide a faster algorithm for computing the diameter that runs in $O(n^2 \log n)$ time.
-
Computing the $$L_1$$L1 Geodesic Diameter and Center of a Polygonal Domain
Discrete & Computational Geometry, 2016Co-Authors: Sang Won Bae, Matias Korman, Yoshio Okamoto, Valentin Polishchuk, Joseph S. B. Mitchell, Haitao WangAbstract:For a Polygonal Domain with h holes and a total of n vertices, we present algorithms that compute the $$L_1$$L1 geodesic diameter in $$O(n^2+h^4)$$O(n2+h4) time and the $$L_1$$L1 geodesic center in $$O((n^4+n^2 h^4)\alpha (n))$$O((n4+n2h4)ź(n)) time, respectively, where $$\alpha (\cdot )$$ź(·) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in $$O(n^{7.73})$$O(n7.73) or $$O(n^7(h+\log n))$$O(n7(h+logn)) time, and compute the geodesic center in $$O(n^{11}\log n)$$O(n11logn) time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on $$L_1$$L1 shortest paths in Polygonal Domains.
Kyungyong Chwa - One of the best experts on this subject based on the ideXlab platform.
-
the geodesic farthest site voronoi diagram in a Polygonal Domain with holes
Symposium on Computational Geometry, 2009Co-Authors: Sang Won Bae, Kyungyong ChwaAbstract:We investigate the farthest-site Voronoi diagram of k point sites with respect to the geodesic distance in a Polygonal Domain of n corners and h (≥ 0) holes. In the case of h=0, Aronov et al. [2] in 1993 proved that there are at most O(k) faces in the diagram and the complexity of the diagram is at most O(n+k). However, any nontrivial upper bound on the geodesic farthest-site Voronoi diagram in a Polygonal Domain when h > 0 remains unknown afterwards. In this paper, we show that the diagram in a Polygonal Domain consists of Θ(hk) faces and its total combinatorial complexity is Θ(nk) in the worst case for any h ≥ 1. Interestingly, the worst-case complexity of the diagram is independent from the number h of holes if h ≥ 1 while the maximum possible number of faces is dependent on h rather than on the complexity n of the Polygonal Domain. Also, we present an O(nk log2(n+k) log k)-time algorithm that constructs the diagram explicitly.
-
Symposium on Computational Geometry - The geodesic farthest-site Voronoi diagram in a Polygonal Domain with holes
Proceedings of the 25th annual symposium on Computational geometry - SCG '09, 2009Co-Authors: Sang Won Bae, Kyungyong ChwaAbstract:We investigate the farthest-site Voronoi diagram of k point sites with respect to the geodesic distance in a Polygonal Domain of n corners and h (≥ 0) holes. In the case of h=0, Aronov et al. [2] in 1993 proved that there are at most O(k) faces in the diagram and the complexity of the diagram is at most O(n+k). However, any nontrivial upper bound on the geodesic farthest-site Voronoi diagram in a Polygonal Domain when h > 0 remains unknown afterwards. In this paper, we show that the diagram in a Polygonal Domain consists of Θ(hk) faces and its total combinatorial complexity is Θ(nk) in the worst case for any h ≥ 1. Interestingly, the worst-case complexity of the diagram is independent from the number h of holes if h ≥ 1 while the maximum possible number of faces is dependent on h rather than on the complexity n of the Polygonal Domain. Also, we present an O(nk log2(n+k) log k)-time algorithm that constructs the diagram explicitly.
