Source author record

Ankush Acharyya

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Minimum color spanning circle of imprecise points

Let $\cal R$ be a set of $n$ colored imprecise points, where each point is colored by one of $k$ colors. Each imprecise point is specified by a unit disk in which the point lies. We study the problem of computing the smallest and the largest possible minimum color spanning circle, among all possible choices of points inside their corresponding disks. We present an $O(nk\log n)$ time algorithm to compute a smallest minimum color spanning circle. Regarding the largest minimum color spanning circle, we show that the problem is NP-Hard and present a $\frac{1}{3}$ -factor approximation algorithm. We improve the approximation factor to $\frac{1}{2}$ for the case where no two disks of distinct color intersect.

preprint2017arXiv

Range Assignment of Base-Stations Maximizing Coverage Area without Interference

We study the problem of assigning non-overlapping geometric objects centered at a given set of points such that the sum of area covered by them is maximized. If the points are placed on a straight-line and the objects are disks, then the problem is solvable in polynomial time. However, we show that the problem is NP-hard even for simplest objects like disks or squares in ${\mathbb{R}}^2$ . Eppstein [CCCG, pages 260--265, 2016] proposed a polynomial time algorithm for maximizing the sum of radii (or perimeter) of non-overlapping balls or disks when the points are arbitrarily placed on a plane. We show that Eppstein's algorithm for maximizing sum of perimeter of the disks in ${\mathbb{R}}^2$ gives a $2$ -approximation solution for the sum of area maximization problem. We propose a PTAS for our problem. These approximation results are extendible to higher dimensions. All these approximation results hold for the area maximization problem by regular convex polygons with even number of edges centered at the given points.

preprint2016arXiv

Color Spanning Annulus: Square, Rectangle and Equilateral Triangle

In this paper, we study different variations of minimum width color-spanning annulus problem among a set of points $P=\{p_1,p_2,\ldots,p_n\}$ in $I\!\!R^2$ , where each point is assigned with a color in $\{1, 2, \ldots, k\}$ . We present algorithms for finding a minimum width color-spanning axis parallel square annulus $(CSSA)$ , minimum width color spanning axis parallel rectangular annulus $(CSRA)$ , and minimum width color-spanning equilateral triangular annulus of fixed orientation $(CSETA)$ . The time complexities of computing (i) a $CSSA$ is $O(n^3+n^2k\log k)$ which is an improvement by a factor $n$ over the existing result on this problem, (ii) that for a $CSRA$ is $O(n^4\log n)$ , and for (iii) a $CSETA$ is $O(n^3k)$ . The space complexity of all the algorithms is $O(k)$ .

preprint2016arXiv

Covering segments with unit squares

We study several variations of line segment covering problem with axis-parallel unit squares in $I\!\!R^2$ . A set $S$ of $n$ line segments is given. The objective is to find the minimum number of axis-parallel unit squares which cover at least one end-point of each segment. The variations depend on the orientation and length of the input segments. We prove some of these problems to be NP-complete, and give constant factor approximation algorithms for those problems. For some variations, we have polynomial time exact algorithms. For the general version of the problem, where the segments are of arbitrary length and orientation, and the squares are given as input, we propose a factor 16 approximation result based on multilevel linear programming relaxation technique, which may be useful for solving some other problems. Further, we show that our problems have connections with the problems studied by Arkin et al. 2015 on conflict-free covering problem. Our NP-completeness results hold for more simplified types of objects than those of Arkin et al. 2015.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.