We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are $O(n^3)$ and $O(n^2)$, respectively. For a penny graph, our proposed 2-approximation algorithm works in $O(n\log n)$ time using $O(n)$ space. We also propose a polynomial-time approximation scheme (PTAS) for the maximum independent set problem for a unit disk graph. Given an integer $k > 1$, it produces a solution of size $\frac{1}{(1+\frac{1}{k})^2}|OPT|$ in $O(k^4n^{\sigma_k\log k}+n\log n)$ time and $O(n+k\log k)$ space, where $OPT$ is the subset of disks in an optimal solution and $\sigma_k\leq\frac{7k}{3}+2$. For a penny graph, the proposed PTAS produces a solution of size $\frac{1}{(1+\frac{1}{k})}|OPT|$ in $O(2^{2\sigma_k}nk+n\log n)$ time using $O(2^{\sigma_k}+n)$ space.

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 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: \begin{itemize} \item[$\bullet$] computing the minimum enclosing circle (\MEC) of a set of $n$ points in $\IR^{\mbox{2}}$, and \item[$\bullet$] linear programming problems with two and three variables and $n$ constraints. \end{itemize} 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.

In this paper, we study the problem of designing in-place algorithms for finding the maximum clique in the {\it intersection graphs} of axis-parallel rectangles and disks in $\IR^2$. First, we propose an $O(n^2\log n)$ time in-place algorithm for finding the maximum clique of the intersection graph of a set of $n$ axis-parallel rectangles of arbitrary sizes. For the intersection graph of fixed height rectangles, the time complexity can be slightly improved to $O(n\log n+nK)$, where $K$ is the size of the maximum clique. For disk graphs, we consider two variations of the maximum clique problem, namely geometric clique and graphical clique. The time complexity of our algorithm for finding the largest geometric clique is $O(m\log n+n^2)$ where $m$ is the number of edges in the disk graph, and it works for disks of arbitrary radii. For graphical clique, our proposed algorithm works for unit disks (i.e., of same radii) and the worst case time complexity is $O(n^2+m(n+K^3))$; $m$ is the number of edges in the unit disk intersection graph and $K$ is the size of the largest clique in that graph. It uses $O(n^3)$ time in-place computation of maximum matching in a bipartite graph, where the vertices are given in an array, and the existence of an edge between a pair of vertices can be checked by an oracle on demand (from problem specification) in $O(1)$ time. This problem is of independent interest. All these algorithms need $O(1)$ work space in addition to the input array.

In this paper, we consider constant factor approximation algorithms for a variant of the discrete piercing set problem for unit disks. Here a set of points $P$ is given; the objective is to choose minimum number of points in $P$ to pierce the unit disks centered at all the points in $P$. We first propose a very simple algorithm that produces 12- approximation result in $O(n\log n)$ time. Next, we improve the approximation factor to 4 and then to 3. The worst case running time of these algorithms are $O(n^8\log n)$ and $O(n^{15}\log n)$ respectively. Apart from the space required for storing the input, the extra work-space requirement of all these algorithms are $O(1)$. Finally, we propose a PTAS for the same problem. Given a positive integer $k$, it can produce a solution with performance ratio $(1+\frac{1}{k})^2$ in $O(n^{O(k)})$ time.

One of the classic data structures for storing point sets in $\IR^2$ is the priority search tree, introduced by McCreight in 1985. We show that this data structure can be made in-place, i.e., it can be stored in an array such that each entry stores only one point of the point set and no entry is stored in more than one location of that array. It combines a binary search tree with a heap. We show that all the standard query operations can be performed within the same time bounds as for the original priority search tree, while using only $O(1)$ extra space.
We introduce the min-max priority search tree which is a combination of a binary search tree and a min-max heap. We show that all the standard queries which can be done in two separate versions of a priority search tree can be done with a single min-max priority search tree.
As an application, we present an in-place algorithm to enumerate all maximal empty axis-parallel rectangles amongst points in a rectangular region $R$ in $\IR^2$ in $O(m \log n)$ time with $O(1)$ extra-space, where $m$ is the total number of maximal empty rectangles.

Space efficient algorithms for the maximum independent set problem for interval graphs and trees are presented in this paper. For a given set of $n$ intervals on a real line, we can compute the maximum independent set in $O(\frac{n^2}{s}+n\log s)$ time using $O(s)$ extra-space. The lower bound of the $time \times space$ product for this problem is $\Omega(n^{2-\epsilon})$, where $\epsilon = O(1/ \sqrt{\log n})$. We also propose an $(1+\frac{1}{\epsilon})$ approximation algorithm for this problem that executes $O(\frac{1}{\epsilon})$ passes over the read-only input tape and uses $O(k)$ extra space, where $k$ is the size of the reported answers. For trees with $n$ nodes, our proposed $\frac{5}{3}$-approximation algorithm runs in $O(n)$ time using $O(1)$ extra-space.

This paper addresses the problem of locating two facilities in vertex-weighted tree/cycle/unicyclic networks, where each facility can fail with a given probability~\cite{snyder2005}. It is assumed that the two facilities do not fail simultaneously, and when a facility fails, the other facility is required to service all the vertices. We show that the weighted {\em back-up 2-center} on a path (resp. tree, cycle, unicyclic) network can be computed in $O(n)$ (resp. $O(n\log n)$, $O(n^2)$, $O(n^2\log n)$) time, where $n$ is the number of vertices, and the centers need not be at vertices. This is the first sub-quadratic time result for vertex-weighted tree networks. For vertex-unweighted trees, it runs in $O(n)$ time, matching the best known result~\cite{wang2009}. The algorithm remains linear when there are only a constant number of distinct weights.

Asano et al. [JoCG 2011] proposed an open problem of computing the minimum enclosing circle of a set of $n$ points in $\IR^{\mbox{2}}$ given in a read-only array in sub-quadratic time. We show that Megiddo's prune and search algorithm for computing the minimum radius circle enclosing the given points can be tailored to work in a read-only environment in $O(n^{1+\epsilon})$ time using $O(\log n)$ extra space, where $\epsilon$ is a positive constant less than 1. As a warm-up, we first solve the same problem in an {\it in-place} setup in linear time with $O(1)$ extra space.

We consider constant factor approximation algorithms for a variation of the discrete piercing set problem for unit disks. Here a set of points $P$ is given; the objective is to choose minimum number of points in $P$ to pierce all disks of unit radius centered at the points in $P$. We first propose a very simple algorithm that produces a 14-factor approximation result in $O(n\log n)$ time. Next, we improve approximation factor to 4 and then to 3. Both algorithms run in polynomial time.