Search

We study a space-efficient algorithm for computing a centerpoint for a set P of n points in R 2 , where the points in P are given in a read-only array. We propose an algorithm that finds a centerpoint of P in O ( T ( n 2 ) log 3 ⁡ n ) time using O ( S ( n 2 ) ) extra space, where T ( n ) and S ( n ) are the time and extra space complexities of computing the median among a set of n elements stored in a read-only array. We also present the applications of this algorithm for computing the Tukey depth and k -hull of a point set in R 2 . [ABSTRACT FROM AUTHOR]

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]

This paper deals with an important problem of mobile communication. The objective is to place k base stations of equal range on the boundary of a convex polygonal region P such that each point inside P is covered by at least one base station. We name this problem as region-cover(k) problem. A simplified form of this problem is the vertex-cover(k) problem, where the objective is to communicate with only the vertices of P instead of covering the entire polygon. We first present efficient algorithms for vertex-cover(2) and region-cover(2) problems, where the base stations are to be installed on a pair of specified edges. The time complexity of these algorithms are O(n log n) and O(n2) respectively, where n is the number of vertices in the polygon P. Next, we consider the case where k ≥ 3. We first concentrate on a restricted version of the vertex-cover(k) and region-cover(k) problems, where all the k base stations are to be installed on the same edge of P. Our proposed algorithm for the restricted vertex-cover(k) problem produces optimum result in O(min(n2,nk log n)) time, whereas the algorithm for the restricted region-cover(k) problem produces an (1 + ∊)-factor approximation result in $O((n + k){\rm log}(n + k) + n{\rm log}(\lceil \frac{1}{\epsilon} \rceil)$ time. Finally, we propose efficient heuristic algorithm for the unrestricted version of the region-cover(k) problem for k ≥ 3. Experimental results demonstrate that our proposed algorithm runs fast and produces near optimum solutions. [ABSTRACT FROM AUTHOR]

Highlights • Algorithms for covering and hitting a given set of line segments by two congruent squares of minimum size is studied. • The algorithm produces optimum solution by sequentially reading the input array (read only) twice. • The extra space complexity of the algorithm is O (1). • A restricted version of covering is also studied where each object is to be completely covered by at least one square. • This algorithm gives 2 approximation result to cover/hit the segments with two congruent disks of minimum size. Abstract This paper discusses the problem of covering and hitting a set of line segments L in R 2 by a pair of axis-parallel congruent squares of minimum size. We also discuss the restricted version of covering, where each line segment in L is to be covered completely by at least one square. The proposed algorithms assume that the input segments are given in a read-only array. For each of these problems (i.e. covering , hitting and restricted covering problems), our proposed algorithm reports the optimum result by executing only two passes of reading the input array sequentially. All these algorithms need only O (1) extra space. The solution of these problems also give a 2 approximation for covering and hitting those line segments L by two congruent disks of minimum radius with same computational complexity. [ABSTRACT FROM AUTHOR]

We study the rectilinear path problem in the presence of disjoint axis parallel rectangular obstacles in the read-only and in-place setup. The input to the problem is a set R of n axis-parallel rectangular obstacles in R 2 . The objective is to answer the following query efficiently. Path-Query ( p , q ) : Given a pair of points p and q , report an axis-parallel path from p to q avoiding the obstacles in R . In the read-only setup, we show that Path-Query ( p , q ) problem can be solved in O ( n 2 s + n log s ) time using O ( s ) extra space. We also show that the existence of an x -monotone path and reporting it, if it exists, can be done with the same asymptotic time complexity. If the objective is to test the existence of an x y -monotone path between the given pair of points p and q avoiding the obstacles, and report it if exists, then our proposed algorithm needs O ( n 2 s + n log s + M s log n ) time with O ( s ) extra space, where M s is the time complexity for computing the median of n elements in the read-only setup using O ( s ) extra space. Finally, we show that when the obstacles are unit squares instead of rectangles of arbitrary size, then there always exists a path of O ( n ) links between a pair of query points, and the path can be reported in O ( n n ) time using O ( 1 ) extra work-space. It is also shown that there is an instance where the minimum number of links in a path between a pair of specified points is O ( n ) . The objective of the Path-Query ( p , q ) in the in-place setup is to preprocess the input rectangles in a data structure in the input array itself such that for any pair of query points p and q , a rectilinear path can be reported efficiently. Here we propose an algorithm with O ( n log n ) preprocessing time and O ( n 3 / 4 + χ ) query time, where χ is the number of links (bends) in the path. Both the preprocessing and query answering need O ( 1 ) extra space. [ABSTRACT FROM AUTHOR]