Search

Prune-and-search is an excellent algorithmic paradigm for solving various optimization problems. We provide a general scheme for prune-and-search technique and show how to implement it in space-efficient manner. We consider both the in-place and read-only model which have several advantages compared to the traditional model of computation. Our technique can be applied to a large number of problems which accept prune-and-search. For examples, we study the following problems each of which has tremendous practical usage apart from theoretical implication: • computing the minimum enclosing circle (MEC) of a set of n points in R 2 , and • linear programming problems with two and three variables and n constraints. In the in-place setting, all these problems can be solved in O ( n ) time using O ( 1 ) extra-space. In the read-only setup, the time and extra-space complexities of the proposed algorithms for all these problems are O ( n polylog ( n ) ) and O ( polylog ( n ) ) , respectively. [ABSTRACT FROM AUTHOR]

Abstract: The coverage problem in wireless sensor networks addresses the problem of covering a region with sensors. Many different definitions of coverage are there in the literature depending on the goal of the coverage. In this paper, we address the problem of determining the quality of a sensor deployment against an intruder who can walk along a straight line. A line segment is said to be k-covered if it intersects the sensing regions of at least sensors distributed in . Similarly, it is said to be k-uncovered if it intersects the sensing regions, that is assumed to be circular, of at most sensors. We introduce two new metrics, smallest -covered line segment and longest -uncovered line segment, for measuring the quality of line coverage achieved by a sensor deployment. The intruder can walk a distance less than the smallest -covered line segment without ever being detected by sensors. So, this metric gives an estimate on the distance an intruder can walk in a straight line path before being detected by sensors. On the other side, the defender would want to deploy sensors so that the length of the longest -uncovered line segment is minimized. Given a deployment of sensors, we propose deterministic algorithms to determine the smallest -covered line segment and longest -uncovered line segment where the line segments can be of the following types: (i) axis-parallel (horizontal and vertical) line segments, (ii) line segments whose one endpoint is fixed and is of arbitrary orientation and (iii) arbitrary line segments. The time complexities for the first and second types of line segments are for both smallest -covered line segment and longest -uncovered line segment, where is the number of intersections among circles. For the arbitrary line segment case, the smallest -covered segment can be determined in time, whereas, the longest -uncovered segment can be determined in time, where and is a small value greater than or equal to . All our algorithms take linear space. [Copyright &y& Elsevier]