# Minati De

Department of Mathematics

Indian Institute of Technology Delhi

- Research Interests
- Publications
- Bio-Sketch
- Teaching
- Professional Activities
- Recognitions
- Some Interesting Links
- Contact

## Research Interests

MathSciNet DBLP

## Preprints

### "Variations of largest rectangle recognition amidst a bichromatic point set"

Ankush Acharyya, Minati De, Subhas C. Nandy, Supantha Pandit### "Range Assignment of Base-Stations Maximizing Coverage Area without Interference"

Ankush Acharyya, Minati De, Subhas C. Nandy, Bodhayan RoyArXiv (Preliminary version appeared in CCCG 2017)

### "Maximum Independent Set for Interval Graphs and Trees in Space Efficient Models"

Binay K. Bhattacharya, Minati De, Subhas C. Nandy, Sasanka Roy### "Geometric Dominating Set and Set Cover via Local Search"

Minati De and Abhiruk LahiriArXiv

### "Facility location problems in the constant work-space read-only memory model"

Binay K. Bhattacharya, Minati De, Subhas C. Nandy, Sasanka RoyArXiv

## Articles in Journals

### "Circular Separation Dimension of a Subclass of Planar Graphs"

Arpitha P. Bharathi, Minati De, Abhiruk LahiriDiscrete Mathematics & Theoretical Computer Science 19:(3)#8

DOI ArXiv

### "Rectilinear Path Problems in Restricted Memory Setup"

Binay K. Bhattacharya, Minati De, Anil Maheshwari, Subhas C. Nandy, Sasanka RoyDiscrete Applied Mathematics 228: 80-87 (2017).

DOI

### "Approximation Algorithms for Computing Maximum Independent Set of a Unit Disk Graph"

Gautam K. Das, Minati De, Sudeshna Kolay, Subhas C. Nandy and Susmita Sur-KolayInformation Processing Letters 115(3): 439-446 (2015)

DOI PDF ⇒ Abstract

*
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 with Limited Work-space"

Minati De, Subhas Nandy and Sasanka RoyJournal of Computer and System Sciences (JCSS), 81(2): 398-414 (2015).

DOI PDF ⇒ Abstract

*
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-place Algorithms for Computing a Largest Clique in Geometric Intersection Graphs"

Minati De, Subhas Nandy and Sasanka RoyDiscrete Applied Mathematics, Volume 178, 11 December 2014, Pages 58–70

Preliminary version appeared in the proceedings of the joint conference FAW-AAIM 2012

DOI PDF ⇒ Abstract

*
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.
*

### "Approximation Algorithms for a Variant of Discrete Piercing Set Problem for Unit Disks"

Minati De, Gautam K. Das, Paz Carmi and Subhas C. NandyInt. J. Computational Geometry and Appl., (Vol. 23, No. 6 (2013) 461–477)

DOI PDF ⇒ Abstract

*
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.
*

### "An In-Place Min-Max Priority Search Tree"

Minati De, Anil Maheshwari, Subhas Nandy and Michiel SmidComputational Geometry: Theory and Application (CGTA) 46(3): 310-327 (2013)

Preliminary version appeared in : The Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011

DOI PDF ⇒ Abstract

*
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.
*

## Articles in Conference Proceedings

### "Approximation Schemes for Geometric Coverage Problems"

Steven Chaplick, Minati De, Alexander Ravsky, Joachim SpoerhaseESA 2018 (To appear)

Also appeared in ICALP 2018 as a brief announcement: DOI/PDF

### "Computing Convex-Straight-Skeleton Voronoi Diagrams for Segments and Convex Polygons"

Gill Barequet, Minati De and Michael T. GoodrichCOCOON 2018: 130-142

DOI PDF

### "Guarding Polyhedral Terrain by k-Watchtowers"

Nitesh Tripathi, Manjish Pal, Minati De, Gautam Das, and Subhas C. NandyFAW 2018: 112-125

DOI PDF

### "Range Assignment of Base-Stations Maximizing Coverage Area without Interference"

Ankush Acharyya, Minati De, Subhas C. NandyCCCG 2017:127-131

PDF [Full version:ArXiv]

### "Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function"

Gill Barequet and Minati DeCALDAM 2017: 24-36

DOI PDF

### "Demand hitting and covering of intervals"

Datta Krupa R, Aniket Basu Roy, Minati De and Sathish GovindarajanCALDAM 2017: 267-280

DOI PDF

### "Rectilinear Path Problems in Restricted Memory Setup"

Binay K. Bhattacharya, Minati De, Anil Maheshwari, Subhas C. Nandy, Sasanka RoyCALDAM 2015: 69-80

DOI

### "Maximum Independent Set for Interval Graphs and Trees in Space Efficient Models"

Binay Bhattacharya, Minati De, Subhas C. Nandy and Sasanka RoyIn the Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014

PDF ⇒ Abstract

*
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.
*

### "Back-up 2-Center on a Path/Tree/Cycle/Unicycle"

Binay Bhattacharya, Minati De, Tsunehiko Kameda, Sasanka Roy, Vladyslav Sokol and Zhao SongIn the proceedings of 20th International Computing and Combinatorics Conference (COCOON'14)

DOI PDF ⇒ Abstract

*
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.
*

### "Minimum Enclosing Circle with Few Extra Variables"

Minati De, Subhas Nandy and Sasanka RoyIn the proceedings of 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science (Page 510-521), FSTTCS 2012

PDF ⇒ Abstract

*
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.
*

### "In-place Algorithms for Computing a Largest Clique in Geometric Intersection Graphs"

Minati De, Subhas Nandy and Sasanka RoyIn the proceedings of the joint conference FAW-AAIM 2012 (page 327-338)

Full version appeared in: Discrete Applied Mathematics, Volume 178, 11 December 2014, Pages 58–70

DOI

### "Approximation Algorithms for the Discrete Piercing Set Problem for Unit Disks"

Minati De, Gautam Das and Subhas NandyThe Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011 (page 375-380), CCCG 2011

PDF ⇒ Abstract

*
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.
*

### "An In-Place Priority Search Tree"

Minati De, Anil Maheshwari, Subhas C. Nandy, Michiel H. M. SmidThe Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011 (page 331-336), CCCG 2011

### "Space-efficient Algorithms for Empty Space Recognition among a Point Set in 2D and 3D"

Minati De, Subhas C. NandyThe Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011 (page 347-352), CCCG 2011

## Dissertations and Thesis

Thesis title: Space-efficient Algorithms for Geometric Optimization Problems

Institute: Indian Statistical Institute, Kolkata

Advisor: Professor Subhas C. Nandy

Title: Algorithms on Geometric Graphs [Won the best dissertation award]

Institute: Indian Statistical Institute, Kolkata

Advisor: Professor Subhas C. Nandy

## Present Affiliation

## Former Affiliations

Host Faculty: Prof. Gill Barequet

Host Faculty: Prof. Binay Bhattacharya

## Education

Thesis Title: Space-efficient Algorithms for Geometric Optimization Problems

Advisor: Prof. Subhas C. Nandy

### “I never teach my pupils, I only attempt to provide the conditions in which they can learn.” ― Albert Einstein

## Teaching

Course webpage can be found: here.

# Courses I Taught in IISc

Targeted Audience: UG Students

Course webpage can be found: here.

(co-taught with Prof. Deepak D'Souza)

Targeted Audience: Faculty of AICTE recognized engineering colleges

(co-taught with Prof. Sunil Chandran)

Targeted Audience: UG Students

Course webpage can be found: here.

Targeted Audience: Mainly for ME SSA students with a few UG Students

Course webpage can be found: here.

(co-taught with Prof. Sathish Govindarajan)

## Professional Activities

⇒ Conferences: SoCG 2017, WALCOM 2017, WALCOM 2016, CCCG 2015, WG 2015, FSTTCS 2014.

⇒ Journal: Networks, Algorithmica.

## Experience

## Recognitions

⇒ Hosted by Dept. of CSA, IISc from January, 2015 to present.

⇒ Hosted by CG Lab, Carleton University during March, 2011 to August, 2011.

⇒ Has been awarded the Sunity Kumar Pal Gold Medal for doing the best dissertation in M.Tech in Computer Science programme in Indian Statistical Institute during 2008-2010.

⇒ Has been awarded as Sports Champion Amongst Girls in the Annual Athletic Meet of Bengal Engineering & Science University, Shibpur in 2005-2006.

⇒ Was considered for an award under National Merit Scholarship of Govt. of India on the result of Higher Secondary examination, 2004.

⇒ Recepient of National scholarship for the talented children in rural areas in the year 2000.

## Some Interesting Links

## Contact

## Dr. Minati De

Department of Mathematics,Indian Institute of Technology Delhi,

Hauz Khas, New Delhi- 110 016, India

Office: Block II 428 E (in between II 428B and II 428C)

E-Mail: minati<AT>maths.iitd.ac.in