Person: Pandit, Supantha
Loading...
Name
Supantha Pandit
Job Title
Faculty
Email Address
Telephone
079-68261546
Birth Date
Specialization
Theoretical Computer Science
Abstract
Biography
Supantha Pandit is an Assistant Professor at the Dhirubhai Ambani Institute of Information and Communication Technology (DA-IICT), Gandhinagar, Gujarat, India. Before joining DA-IICT, he was a SERB Indo-US Post Doctoral Fellow at the SUNY Stony Brook, New York, USA. He was also a SERB National Post Doctoral Fellow at the Indian Statistical Institute Kolkata, India. He obtained his Ph.D. degree in Computer Science and Engineering from the Indian Institute of Technology Ropar, Punjab, India. His current research concentrates on theoretical computer science, mainly focused on computational geometry, approximation algorithms, distributed network algorithms, and graph algorithms.
Research Projects
Organizational Units
Name
12 results
Search Results
Now showing 1 - 10 of 12
Publication Metadata only Dominating set of rectangles intersecting a straight line(Springer, 08-01-2021) Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; DA-IICT, GandhinagarThe Minimum Dominating Set (MDS) problem is one of the well-studied problems in computer science. It is well-known that this problem is�-hard for simple geometric objects; unit disks, axis-parallel unit squares, and axis-parallel rectangles to name a few. An interesting variation of the�MDS�problem with rectangles is when there exists a straight line that intersects each of the given rectangles. In the recent past researchers have studied the maximum independent set, minimum hitting set problems on this setting with different geometric objects. We study the�MDS�problem with axis-parallel rectangles, unit-height rectangles, and unit squares in the plane. These geometric objects are constrained to be intersected by a straight line. For axis-parallel rectangles, we prove that this problem is�-hard. When the objects are axis-parallel unit squares, we present a polynomial time algorithm using dynamic programming. We provide a polynomial time algorithm for unit-height rectangles as well. For unit squares that touch the straight line at a single point from either side of the straight line, we show that there is an�-time algorithm.Publication Metadata only Variations of largest rectangle recognition amidst a bichromatic point set(Elsevier, 01-11-2020) Acharyya, Ankush; Deb, Minati; Nandy, Subhas C; Pandit, Supantha; DA-IICT, GandhinagarClassical�separability�problem involving multi-color point sets is an important area of study in�computational geometry. In this paper, we study different separability problems for bichromatic point set��in��and�, where��and��represent a set of��red points and a set of��blue points respectively, and the objective is to compute a monochromatic object of a desired type and of maximum size. We propose in-place algorithms for computing (i) an arbitrarily oriented monochromatic rectangle of maximum size in�, and (ii) an axis-parallel monochromatic cuboid of maximum size in�. The time complexities of the algorithms for problems (i) and (ii) are��and�, respectively. As a prerequisite, we propose an in-place construction of the classic data structure the�k-d�tree, that was originally invented by J. L. Bentley in 1975. Our in-place variant of the�-d tree for a set of��points in��supports orthogonal range counting query using��extra workspace, and with��query time complexity. The construction time of this data structure is�. Both the construction and query algorithms are non-recursive in nature that do not need��size recursion stack compared to the previously known construction algorithm for in-place�-d tree and query in it. We believe that this result is of independent interest. We also propose an algorithm for the problem of computing an arbitrarily oriented rectangle of maximum weight among a point set�, where each point in��(resp.�) is associated with a negative (resp. positive) real-valued weight that runs in��time using��extra spacePublication Metadata only Covering and packing of rectilinear subdivision(Elsevier, 01-11-2020) Jana, Satyabrata; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; DA-IICT, GandhinagarWe study a class of geometric covering and packing problems for bounded closed regions on the plane. We are given a set of axis-parallel line segments that induce a planar subdivision with bounded (rectilinear) faces. We are interested in the following problems. (P1) STABBING-SUBDIVISION: Stab all closed bounded faces of the planar subdivision by selecting a minimum number of points in the plane. (P2) INDEPENDENT-SUBDIVISION: Select a maximum size collection of pairwise non-intersecting closed bounded faces of the planar subdivision. (P3) DOMINATING-SUBDIVISION: Select a minimum size collection of bounded faces of the planar subdivision such that every other face of the subdivision that is not selected has a non-empty intersection (i.e., sharing an edge or a vertex) with some selected face. We show that these problems are NP-hard. We even prove that these problems are NP-hard when we concentrate only on the rectangular faces of the subdivision. Further, we provide constant factor approximation algorithms for the STABBING-SUBDIVISION problem.Publication Metadata only Covering and packing of triangles intersecting a straight line(Elsevier, 01-10-2022) Pandit, Supantha; DA-IICT, GandhinagarWe study four geometric optimization problems:�set cover,�hitting set,�piercing set, and�independent set�with�right-triangles�(a triangle is a right-triangle whose base is parallel to the�-axis, perpendicular is parallel to the�-axis, and the slope of the hypotenuse is�). The input triangles are constrained to be intersecting a�straight line. The straight line can either be a�horizontal�or an�inclined�line (a line whose slope is�). A right-triangle is said to be a�-right-triangle, if the length of both its base and perpendicular is�. For 1-right-triangles�where the triangles intersect an inclined line, we prove that the set cover and hitting set problems are�-hard, whereas the piercing set and independent set problems are in�. The same results hold for 1-right-triangles�where the triangles are intersecting a horizontal line instead of an inclined line. We prove that the piercing set and independent set problems with right-triangles�intersecting an inclined line are�-hard. Finally, we give an��time exact algorithm for the independent set problem with�-right-triangles�intersecting a straight line such that��takes more than one value from�, for some integer�. We also present�-time dynamic programming algorithms for the independent set problem with 1-right-triangles�where the triangles intersect a horizontal line and an inclined line.Publication Metadata only Burning and w-burning of geometric graphs(Elsevier, 15-09-2023) Gorain, Barun; Gupta, Arya T; Lokhande, Swapnil A; Mondal, Kaushik; Pandit, Supantha; DA-IICT, GandhinagarGraph burning runs on discrete time-steps. The aim is to burn all the vertices in a given graph using a minimum number of time-steps. This number is known to be the burning number of the graph. The spread of social influence, an alarm, or a social contagion can be modeled using graph burning. The less the burning number, the faster the spread.It is well-known that the optimal burning of general graphs is NP-complete. Further, graph burning has been shown to be NP-complete on a vast majority classes of graphs.Approximation results also exist for several graph classes. In this article, we show that the burning problem is NP-complete on connected interval graphs and permutation graphs. We also study the burning properties of grids. More precisely, we show that the lower bound of the burning number of a grid is at least . We provide a 2-approximation for burning a square grid.We extend the study of the -burning problem, a variation of the graph burning problem where we allow a constant number of vertices to be burnt in any time-step. We prove that -burning of interval, spider, and permutation graphs are NP-complete for any constant . We also provide a 2-approximation for the -burning problem on trees.Publication Metadata only Maximum independent and disjoint coverage(Springer, 01-05-2020) Dhar, Amit Kumar; Madireddy, Raghunath Reddy; Pandit, Supantha; Singh, Jagpreet; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; DA-IICT, GandhinagarSet cover is one of the most studied optimization problems in Computer Science. In this paper, we target two interesting variations of this problem in a geometric setting: (i)�maximum disjoint coverage�(MDC), and (ii)�maximum independent coverage�(MIC) problems. In both problems, the input consists of a set�P�of points and a set�O�of geometric objects in the plane. The objective is to maximize the number of points covered by a set��of selected objects from�O. In the�MDC�problem we restrict the objects in��are pairwise disjoint (non-intersecting). Whereas, in the�MIC�problem any pair of objects in��should not share a point from�P�(however, they may intersect each other). We consider various geometric objects as covering objects such as axis-parallel infinite lines, axis-parallel line segments, unit disks, axis-parallel unit squares, and intervals on a real line. For the covering objects axis-parallel infinite lines, we show that both�MDC�and�MIC�problems admit polynomial time algorithms. In addition to that, we give polynomial time algorithms for both�MDC�and�MIC�problems with intervals on the real line. On the other hand, we prove that the�MIC�problem is�-complete when the objects are horizontal infinite lines and vertical segments. We also prove that both�MDC�and�MIC�problems are�-complete for axis-parallel unit segments in the plane. For unit disks and axis-parallel unit squares, we prove that both these problems are�-complete. Further, we present��es for the�MDC�problem for unit disks as well as unit squares using Hochbaum and Maass�s �shifting strategy�. For unit squares, we design a��for the�MIC�problem using Chan and Hu�s �mod-one transformation� technique.Publication Metadata only Optimal deterministic distributed algorithms for maximal independent set in geometric graphs(Elsevier, 01-10-2019) Molla, Anisur Rahaman; Roy, Sasanka; Pandit, Supantha; DA-IICT, GandhinagarDimensionality reduction techniques based on manifold learning are becoming very popular for computer vision tasks like image recognition and image classification. Generally, most of these techniques involve optimizing a cost function in L2-norm and thus they are susceptible to outliers. However, recently, due to capability of handling outliers, L1-norm optimization is drawing the attention of researchers. The work documented here is the first attempt towards the same goal where orthogonal neighbourhood preserving projection (ONPP) technique is performed using optimization in terms of L1-norm to handle data having outliers. In particular, the relationship between ONPP and PCA is established theoretically in the light of L2-norm and then ONPP is optimized using an already proposed mechanism of PCA-L1. Extensive experiments are performed on synthetic as well as real data for applications like classification and recognition. It has been observed that when larger number of training data is available L1-ONPP outperforms its counterpart L2-ONPP.Publication Metadata only Minimum Membership Covering and Hitting(Elsevier, 12-07-2021) SBMitchella, Joseph; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; DA-IICT, GandhinagarSet Cover is a well-studied problem with application in many fields. A well-known variant of this problem is the Minimum Membership Set Cover problem: Given a set of points and a set of objects, the objective is to cover all points while minimizing the maximum number of objects that contain any one point. A dual of this problem is the Minimum Membership Hitting Set problem: Given a set of points and a set of objects, the objective is to stab all of the objects while minimizing the maximum number of points that an object contains. We study both of these variants in a geometric setting with various types of geometric objects in the plane, including axis-parallel�line segments, axis-parallel strips, rectangles that are anchored on a horizontal line from one side, rectangles that are stabbed by a horizontal line, and rectangles that are anchored on one of two horizontal lines (i.e., each rectangle shares its top or its bottom edge (or both) with one of the input horizontal lines). For each of these problems we either prove NP-hardness or we give a polynomial-time algorithm. In particular, we show that it is NP-complete to decide whether there exists a solution with depth exactly 1 for either the Minimum Membership Set Cover or the Minimum Membership Hitting Set problem. In addition, we study a generalized version of the Minimum Membership Hitting Set problem.Publication Metadata only Pebble guided optimal treasure hunt in anonymous graphs(Elsevier, 24-06-2022) Gorain, Barun; Mondal, Kaushik; Nayak, Himadri; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; Pandit, Supantha; DA-IICT, GandhinagarWe study the problem of treasure hunt in a graph by a mobile agent. The nodes in the graph are anonymous and the edges at any node v of degree deg(v) are labeled arbitrarily as 0,1,�,deg(v)?1. A mobile agent, starting from a node, must find a stationary object, called treasure that is located on an unknown node at a distance D from its initial position. The agent finds the treasure when it reaches the node where the treasure is present. The time of treasure hunt is defined as the number of edges the agent visits before it finds the treasure. The agent does not have any prior knowledge about the graph or the position of the treasure. An Oracle, that knows the graph, the initial position of the agent, and the position of the treasure, places some pebbles on the nodes, at most one per node, of the graph to guide the agent towards the treasure. We target to answer the question: what is the fastest possible treasure hunt algorithm regardless of the number of pebbles are placed? We show an algorithm that uses O(Dlog??) pebbles to find the treasure in a graph G in time O(Dlog??), where ? is the maximum degree of a node in G and D is the distance from the initial position of the agent to the treasure. We show a matching lower bound of ?(Dlog??) on time of the treasure hunt using any number of pebbles.Publication Metadata only Distributed Independent Sets in Interval and Segment Intersection Graphs(World Scientific, 01-01-2025) Bhatt, Nirmala; Gorain, Barun; Mondal, Kaushik; Pandit, Supantha; DA-IICT, Gandhinagar