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

Kyungyong Chwa - One of the best experts on this subject based on the ideXlab platform.

  • optimization algorithms for sweeping a Polygonal Region with mobile guards
    International Symposium on Algorithms and Computation, 2001
    Co-Authors: Sangmin Park, Kyungyong Chwa
    Abstract:

    We study the problem of sweeping a simple polygon using a chain of mobile guards. The basic question is as follows: Given a simple polygon P in the plane, is it possible for two guards to simultaneously walk along the boundary of P from one point to another point in such a way that two guards are always mutually visible and any target moving continuously inside P should eventually lie on the line segment between two guards? It is known that an O(n2)-time algorithm can decide this question. Our contribution is to present efficient algorithms for the following optimization problems: - Given an n-sided polygon, we present an O(n2 log n)-time algorithm for computing a shortest walk in which the total length of the paths that two guards traverse is minimized. - Given an n-sided polygon, we present an O(n2)-time algorithm for computing a minimum diameter walk in which the maximum distance between two guards is minimized. Finally we allow more than two guards. Here the guards should form a simple chain within the polygon such that any consecutive two guards along the chain are mutually visible and the first and last guard have to move along the boundary but others do not. - We present an O(n2)-time algorithm for computing the minimum number of guards to sweep an n-sided polygon and an O(n3)-time algorithm for computing such a schedule.

  • ISAAC - Optimization Algorithms for Sweeping a Polygonal Region with Mobile Guards
    Algorithms and Computation, 2001
    Co-Authors: Sangmin Park, Kyungyong Chwa
    Abstract:

    We study the problem of sweeping a simple polygon using a chain of mobile guards. The basic question is as follows: Given a simple polygon P in the plane, is it possible for two guards to simultaneously walk along the boundary of P from one point to another point in such a way that two guards are always mutually visible and any target moving continuously inside P should eventually lie on the line segment between two guards? It is known that an O(n2)-time algorithm can decide this question. Our contribution is to present efficient algorithms for the following optimization problems: - Given an n-sided polygon, we present an O(n2 log n)-time algorithm for computing a shortest walk in which the total length of the paths that two guards traverse is minimized. - Given an n-sided polygon, we present an O(n2)-time algorithm for computing a minimum diameter walk in which the maximum distance between two guards is minimized. Finally we allow more than two guards. Here the guards should form a simple chain within the polygon such that any consecutive two guards along the chain are mutually visible and the first and last guard have to move along the boundary but others do not. - We present an O(n2)-time algorithm for computing the minimum number of guards to sweep an n-sided polygon and an O(n3)-time algorithm for computing such a schedule.

  • visibility based pursuit evasion in a Polygonal Region by a searcher
    International Colloquium on Automata Languages and Programming, 2001
    Co-Authors: Sangmin Park, Kyungyong Chwa
    Abstract:

    We consider the most basic visibility-based pursuit-evasion problem defined as follows: Given a Polygonal Region, a searcher with 360° vision, and an unpredictable intruder that is arbitrarily faster than the searcher, plan the motion of the searcher so as to see the intruder. In this paper, we present simple necessary and sufficient conditions for a polygon to be searchable, which settles a decade-old open problem raised in [13]. We also show that every searchable polygon is also searchable by a searcher with two flashlights (that is, two ray visions). This implies, combined with the previous work [7], that there is an O(n2)-time algorithm for constructing a search path for an n-sided polygon.

  • ICALP - Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher
    Automata Languages and Programming, 2001
    Co-Authors: Sangmin Park, Kyungyong Chwa
    Abstract:

    We consider the most basic visibility-based pursuit-evasion problem defined as follows: Given a Polygonal Region, a searcher with 360° vision, and an unpredictable intruder that is arbitrarily faster than the searcher, plan the motion of the searcher so as to see the intruder. In this paper, we present simple necessary and sufficient conditions for a polygon to be searchable, which settles a decade-old open problem raised in [13]. We also show that every searchable polygon is also searchable by a searcher with two flashlights (that is, two ray visions). This implies, combined with the previous work [7], that there is an O(n2)-time algorithm for constructing a search path for an n-sided polygon.

Sangmin Park - One of the best experts on this subject based on the ideXlab platform.

  • optimization algorithms for sweeping a Polygonal Region with mobile guards
    International Symposium on Algorithms and Computation, 2001
    Co-Authors: Sangmin Park, Kyungyong Chwa
    Abstract:

    We study the problem of sweeping a simple polygon using a chain of mobile guards. The basic question is as follows: Given a simple polygon P in the plane, is it possible for two guards to simultaneously walk along the boundary of P from one point to another point in such a way that two guards are always mutually visible and any target moving continuously inside P should eventually lie on the line segment between two guards? It is known that an O(n2)-time algorithm can decide this question. Our contribution is to present efficient algorithms for the following optimization problems: - Given an n-sided polygon, we present an O(n2 log n)-time algorithm for computing a shortest walk in which the total length of the paths that two guards traverse is minimized. - Given an n-sided polygon, we present an O(n2)-time algorithm for computing a minimum diameter walk in which the maximum distance between two guards is minimized. Finally we allow more than two guards. Here the guards should form a simple chain within the polygon such that any consecutive two guards along the chain are mutually visible and the first and last guard have to move along the boundary but others do not. - We present an O(n2)-time algorithm for computing the minimum number of guards to sweep an n-sided polygon and an O(n3)-time algorithm for computing such a schedule.

  • ISAAC - Optimization Algorithms for Sweeping a Polygonal Region with Mobile Guards
    Algorithms and Computation, 2001
    Co-Authors: Sangmin Park, Kyungyong Chwa
    Abstract:

    We study the problem of sweeping a simple polygon using a chain of mobile guards. The basic question is as follows: Given a simple polygon P in the plane, is it possible for two guards to simultaneously walk along the boundary of P from one point to another point in such a way that two guards are always mutually visible and any target moving continuously inside P should eventually lie on the line segment between two guards? It is known that an O(n2)-time algorithm can decide this question. Our contribution is to present efficient algorithms for the following optimization problems: - Given an n-sided polygon, we present an O(n2 log n)-time algorithm for computing a shortest walk in which the total length of the paths that two guards traverse is minimized. - Given an n-sided polygon, we present an O(n2)-time algorithm for computing a minimum diameter walk in which the maximum distance between two guards is minimized. Finally we allow more than two guards. Here the guards should form a simple chain within the polygon such that any consecutive two guards along the chain are mutually visible and the first and last guard have to move along the boundary but others do not. - We present an O(n2)-time algorithm for computing the minimum number of guards to sweep an n-sided polygon and an O(n3)-time algorithm for computing such a schedule.

  • visibility based pursuit evasion in a Polygonal Region by a searcher
    International Colloquium on Automata Languages and Programming, 2001
    Co-Authors: Sangmin Park, Kyungyong Chwa
    Abstract:

    We consider the most basic visibility-based pursuit-evasion problem defined as follows: Given a Polygonal Region, a searcher with 360° vision, and an unpredictable intruder that is arbitrarily faster than the searcher, plan the motion of the searcher so as to see the intruder. In this paper, we present simple necessary and sufficient conditions for a polygon to be searchable, which settles a decade-old open problem raised in [13]. We also show that every searchable polygon is also searchable by a searcher with two flashlights (that is, two ray visions). This implies, combined with the previous work [7], that there is an O(n2)-time algorithm for constructing a search path for an n-sided polygon.

  • ICALP - Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher
    Automata Languages and Programming, 2001
    Co-Authors: Sangmin Park, Kyungyong Chwa
    Abstract:

    We consider the most basic visibility-based pursuit-evasion problem defined as follows: Given a Polygonal Region, a searcher with 360° vision, and an unpredictable intruder that is arbitrarily faster than the searcher, plan the motion of the searcher so as to see the intruder. In this paper, we present simple necessary and sufficient conditions for a polygon to be searchable, which settles a decade-old open problem raised in [13]. We also show that every searchable polygon is also searchable by a searcher with two flashlights (that is, two ray visions). This implies, combined with the previous work [7], that there is an O(n2)-time algorithm for constructing a search path for an n-sided polygon.

Dominique Barba - One of the best experts on this subject based on the ideXlab platform.

  • ICIP (2) - Joint tracking of Polygonal and triangulated meshes of objects in moving sequences with time varying content
    Proceedings 2001 International Conference on Image Processing (Cat. No.01CH37205), 2001
    Co-Authors: Ahmad Mahboubi, Jenny Benois-pineau, Dominique Barba
    Abstract:

    This paper proposes a method for tracking of objects contained in video sequences. Each video object is represented both by a triangulated mesh and a Polygonal mesh. The tracking of such models along a moving sequence is based on a full Region-based Polygonal tracking. The triangulated mesh is a union of Delaunay meshes on each Polygonal Region of the VOP. The mesh is articulated, that is, each Polygonal Region in a VOP is Delaunay-triangulated separately and all partial meshes are connected in the global triangulation. Tracking of triangulated meshes is based on detecting and indexing new objects in the video scene along the time in a Polygonal tracking phase.

  • Joint tracking of Polygonal and triangulated meshes of objects in moving sequences with time varying content
    Proceedings 2001 International Conference on Image Processing (Cat. No.01CH37205), 2001
    Co-Authors: Ahmad Mahboubi, Jenny Benois-pineau, Dominique Barba
    Abstract:

    This paper proposes a method for tracking of objects contained in video sequences. Each video object is represented both by a triangulated mesh and a Polygonal mesh. The tracking of such models along a moving sequence is based on a full Region-based Polygonal tracking. The triangulated mesh is a union of Delaunay meshes on each Polygonal Region of the VOP. The mesh is articulated, that is, each Polygonal Region in a VOP is Delaunay-triangulated separately and all partial meshes are connected in the global triangulation. Tracking of triangulated meshes is based on detecting and indexing new objects in the video scene along the time in a Polygonal tracking phase.

  • Tracking of hierarchical active meshes for object based manipulation of video content
    2000 TENCON Proceedings. Intelligent Systems and Technologies for the New Millennium (Cat. No.00CH37119), 2000
    Co-Authors: Ahmad Mahboubi, Jenny Benois-pineau, Dominique Barba
    Abstract:

    This paper proposes a method for an accurate tracking of objects contained in video sequences thus allowing access and manipulation of video objects along the time. Each video object is represented both by a triangulated mesh and a Polygonal mesh. The Polygonal mesh results from a bottom up motion-based segmentation of a video sequence. This model is hierarchical: a video object plane (VOP) is the top of a segmentation pyramid. Each level in it is characterized by its proper quality of motion compensation. The triangulated mesh is a union of Delaunay meshes on each Polygonal Region of the VOP. Tracking is realized both on Polygonal and triangulated meshes.

Masafumi Yamashita - One of the best experts on this subject based on the ideXlab platform.

  • searching a Polygonal Region by a group of stationary k searchers
    Information Processing Letters, 2004
    Co-Authors: Masafumi Yamashita, Ichiro Suzuki, Tiko Kameda
    Abstract:

    We study the problem of searching for mobile intruders in a Polygonal Region by stationary searchers having various levels of vision given by the number of flashlights that a searcher carries. We show that (2g - 1) 1-searchers (i.e., 2g - 1 searchers with one flashlight each) are always sufficient, and sometimes necessary, to search a simple Polygonal Region having a guard number g, which is the size of a minimum guard set. We also show that g (h + 1)-searchers (i.e., g searchers with h + 1 flashlights each), and consequently g(h + 1) 1-searchers as well, can always search a Polygonal Region with h ≥ 1 holes having a guard number g.

  • searching a Polygonal Region from the boundary
    International Journal of Computational Geometry and Applications, 2001
    Co-Authors: Ichiro Suzuki, Masafumi Yamashita, Yuichi Tazoe, Tiko Kameda
    Abstract:

    Polygon search is the problem of finding mobile intruders who move unpredictably in a Polygonal Region, using one or more mobile searchers. Different levels of vision are assumed to model the ability of the searchers. In this paper we mainly consider a special case of this problem, termed boundary search, in which a single searcher has to find the intruders from the boundary of the Region. Our main result is that a single searcher whose vision is limited to the ray of a single flashlight is just as capable as a single searcher having a light bulb that gives 360° vision, that is, any polygon that can be searched by the latter from the boundary can also be searched by the former from the boundary. The proof of the equivalence uses another new result, termed Monotonic Extension Theorem, together with a two-dimensional diagram called the planar boundary visibility map that represents the status of the search as a function of time. We partially settle a long-standing conjecture on the equivalence of the abilities of two types of searchers, one having two flashlights and the other having full 360° vision, for the general (non-boundary) polygon search problem.

  • searching for mobile intruders in a Polygonal Region by a group of mobile searchers
    Symposium on Computational Geometry, 2001
    Co-Authors: Masafumi Yamashita, Ichiro Suzuki, Hideki Umemoto, Tsunehiko Kameda
    Abstract:

    The problem of searching for mobile intruders in a Polygonal Region by mobile searchers is considered. A searcher can move continuously inside a polygon holding a flashlight that emits a single ray of light whose direction can be changed continuously. The vision of a searcher at any time instant is limited to the points on the ray. The intruders can move continuously with unbounded speed. We denote by ps(P) the polygon search number of a simple polygon P , which is the number of searchers necessary and sufficient to search P . Let n , r , b , and g be the number of edges, the number of reflex vertices, the bushiness, and the size of a minimum guard set of P , respectively. In this paper we present matching upper and (worst case) lower bounds of 1 + \lfloor log  3 (2b+1) \rfloor on ps(P) . Also upper bounds on ps(P) in terms of n,r , and g are presented;ps(P) ≤ 1 + \lfloor log  3 (n-3) \rfloor, ps(P) ≤ 1 + \lfloor log  3 r \rfloor , and ps(P) ≤ 2 + \lceil log  2 g \rceil . These upper bounds are tight or almost tight in the worst case, since we show that for any natural number s \geq 2 , there is a polygon P such that ps(P) = log  3 (n+1) = log  3 (2r+3) = 1 + log  3 (2g-1) = s .

  • searching for a mobile intruder in a Polygonal Region
    SIAM Journal on Computing, 1992
    Co-Authors: Ichiro Suzuki, Masafumi Yamashita
    Abstract:

    The problem of searching for a mobile intruder in a simple polygon by a single mobile searcher is considered. This paper investigates the capabilities of searchers having different degrees of visibility by introducing the searcher having k flashlights whose visibility is limited to k rays emanating from his position, and the searcher having a point light source who can see in all directions simultaneously. This paper presents necessary and sufficient conditions for a polygon to be searchable by various searchers. The paper also introduces a class of polygons for which the searcher having two flashlights is as capable as the searcher having a point light source, and it gives a simple necessary and sufficient condition for such polygons to be searchable by the searcher having two flashlights. The complexity of generating a search schedule under some of these conditions is also discussed. Many of the results are proved using chord systems that represent the visibility relations among the vertices and edges o...

Ichiro Suzuki - One of the best experts on this subject based on the ideXlab platform.

  • searching a Polygonal Region by a group of stationary k searchers
    Information Processing Letters, 2004
    Co-Authors: Masafumi Yamashita, Ichiro Suzuki, Tiko Kameda
    Abstract:

    We study the problem of searching for mobile intruders in a Polygonal Region by stationary searchers having various levels of vision given by the number of flashlights that a searcher carries. We show that (2g - 1) 1-searchers (i.e., 2g - 1 searchers with one flashlight each) are always sufficient, and sometimes necessary, to search a simple Polygonal Region having a guard number g, which is the size of a minimum guard set. We also show that g (h + 1)-searchers (i.e., g searchers with h + 1 flashlights each), and consequently g(h + 1) 1-searchers as well, can always search a Polygonal Region with h ≥ 1 holes having a guard number g.

  • searching a Polygonal Region from the boundary
    International Journal of Computational Geometry and Applications, 2001
    Co-Authors: Ichiro Suzuki, Masafumi Yamashita, Yuichi Tazoe, Tiko Kameda
    Abstract:

    Polygon search is the problem of finding mobile intruders who move unpredictably in a Polygonal Region, using one or more mobile searchers. Different levels of vision are assumed to model the ability of the searchers. In this paper we mainly consider a special case of this problem, termed boundary search, in which a single searcher has to find the intruders from the boundary of the Region. Our main result is that a single searcher whose vision is limited to the ray of a single flashlight is just as capable as a single searcher having a light bulb that gives 360° vision, that is, any polygon that can be searched by the latter from the boundary can also be searched by the former from the boundary. The proof of the equivalence uses another new result, termed Monotonic Extension Theorem, together with a two-dimensional diagram called the planar boundary visibility map that represents the status of the search as a function of time. We partially settle a long-standing conjecture on the equivalence of the abilities of two types of searchers, one having two flashlights and the other having full 360° vision, for the general (non-boundary) polygon search problem.

  • searching for mobile intruders in a Polygonal Region by a group of mobile searchers
    Symposium on Computational Geometry, 2001
    Co-Authors: Masafumi Yamashita, Ichiro Suzuki, Hideki Umemoto, Tsunehiko Kameda
    Abstract:

    The problem of searching for mobile intruders in a Polygonal Region by mobile searchers is considered. A searcher can move continuously inside a polygon holding a flashlight that emits a single ray of light whose direction can be changed continuously. The vision of a searcher at any time instant is limited to the points on the ray. The intruders can move continuously with unbounded speed. We denote by ps(P) the polygon search number of a simple polygon P , which is the number of searchers necessary and sufficient to search P . Let n , r , b , and g be the number of edges, the number of reflex vertices, the bushiness, and the size of a minimum guard set of P , respectively. In this paper we present matching upper and (worst case) lower bounds of 1 + \lfloor log  3 (2b+1) \rfloor on ps(P) . Also upper bounds on ps(P) in terms of n,r , and g are presented;ps(P) ≤ 1 + \lfloor log  3 (n-3) \rfloor, ps(P) ≤ 1 + \lfloor log  3 r \rfloor , and ps(P) ≤ 2 + \lceil log  2 g \rceil . These upper bounds are tight or almost tight in the worst case, since we show that for any natural number s \geq 2 , there is a polygon P such that ps(P) = log  3 (n+1) = log  3 (2r+3) = 1 + log  3 (2g-1) = s .

  • searching for a mobile intruder in a Polygonal Region
    SIAM Journal on Computing, 1992
    Co-Authors: Ichiro Suzuki, Masafumi Yamashita
    Abstract:

    The problem of searching for a mobile intruder in a simple polygon by a single mobile searcher is considered. This paper investigates the capabilities of searchers having different degrees of visibility by introducing the searcher having k flashlights whose visibility is limited to k rays emanating from his position, and the searcher having a point light source who can see in all directions simultaneously. This paper presents necessary and sufficient conditions for a polygon to be searchable by various searchers. The paper also introduces a class of polygons for which the searcher having two flashlights is as capable as the searcher having a point light source, and it gives a simple necessary and sufficient condition for such polygons to be searchable by the searcher having two flashlights. The complexity of generating a search schedule under some of these conditions is also discussed. Many of the results are proved using chord systems that represent the visibility relations among the vertices and edges o...