Minati De

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.

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 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 2D. We first propose $O(n^2\log n)$ time in-place algorithms for finding the maximum clique of the intersection graphs of a set of axis-parallel rectangles of arbitrary sizes. For the rectangle 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(n^2\log n)$, 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+mK^4)$; $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^4)$ time in-place computation of maximum matching in a bipartite graph, which is of independent interest. All these algorithms need $O(1)$ work space in addition to the input array $\cal R$.

In this paper, we consider the problem of designing in-place algorithms for computing the maximum area empty rectangle of arbitrary orientation among a set of points in 2D, and the maximum volume empty axis-parallel cuboid among a set of points in 3D. If $n$ points are given in an array of size $n$, the worst case time complexity of our proposed algorithms for both the problems is $O(n^3)$; both the algorithms use $O(1)$ extra space in addition to the array containing the input points.

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.