Search

Herein, we consider the continuous 1.5-dimensional(1.5D) terrain guarding problem with two-sided guarding. We provide an x-monotone chain T and determine the minimal number of vertex guards such that all points of T have been two-sided guarded. A point p is two-sided guarded if there exist two vertices vi (left of p) and (right of p) that both see p. A vertex vi sees a point p on T if the line segment connecting vi to p is on or above T. We demonstrate that the continuous 1.5D terrain guarding problem can be transformed to the discrete terrain guarding problem with a finite point set X and that if X is two-sided guarded, then T is also two-sided guarded. Through this transformation, we achieve an optimal algorithm that solves the continuous 1.5D terrain guarding problem under two-sided guarding.

In this paper, we consider the 1.5-dimensional orthogonal terrain guarding problem. In this problem, we assign an x-monotone chain T because each edge is either horizontal or vertical, and determine the minimal number of vertex guards for all vertices of T. A vertex vi sees a point p on T if the line segment connecting vi to p is on or above T. We provide an optimal algorithm with O(n) for a subproblem of the orthogonal terrain guarding problem. In this subproblem, we determine the minimal number of vertex guards for all right(left) convex verteices of T. Finally, we provide a 2-approximation algorithm that solves the 1.5-dimensional orthogonal terrain guarding problem in O(n).

We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire region. An environment is composed of pixels that form a connected subset of the integer grid. There is at most one robot per pixel and robots move horizontally or vertically at unit speed. Robots enter R by means of k>=1 door pixels Robots are primitive finite automata, only having local communication, local sensors, and a constant-sized memory. We first give algorithms for the single-door case (i.e., k=1), analyzing the algorithms both theoretically and experimentally. We prove that our algorithms have optimal makespan 2A-1, where A is the area of R. We next give an algorithm for the multi-door case (k>1), based on a wall-following version of the leader-follower strategy. We prove that our strategy is O(log(k+1))-competitive, and that this bound is tight for our strategy and other related strategies., Comment: 17 pages, 4 figures, Latex, to appear in Workshop on Algorithmic Foundations of Robotics, 2002