Search

Abstract We study several variations of line segment covering problem with axis-parallel unit squares in the plane. Given a set S of n line segments, the objective is to find the minimum number of axis-parallel unit squares that 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 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 16-approximation algorithm based on multilevel linear programming relaxation technique. More precisely, we reduce this problem to the problem of covering points in the plane by a given set of unit squares using linear programming relaxation technique. A linear programming-based 8-approximation algorithm for the later problem yields a 16-approximation result for the former problem. This technique may be of independent interest in solving some other problems. [ABSTRACT FROM AUTHOR]

Given a set P = { p 1 , p 2 , … , p n } of n points in Image 1 and each assigned with one of the given k distinct colors, we study the problem of finding the minimum width color spanning annulus of different shapes. Specifically, we consider the color spanning circular annulus ( C S C A ), axis-parallel square annulus ( C S S A ), axis parallel rectangular annulus ( C S R A ) , and equilateral triangular annulus of fixed orientation ( C S E T A ) . The time complexities of the proposed algorithms for the respective problems are (i) O ( n 3 log ⁡ n ) for C S C A , (ii) O ( n 3 + n 2 k log ⁡ k ) for C S S A , (iii) O ( n 4 ) for C S R A , and (iv) O ( n 2 k ) for C S E T A . [ABSTRACT FROM AUTHOR]

In this paper, we study variants of the classical geometric shortest path problem inside a simple polygon, where we allow a part of the path to go outside the polygon. Let P be a simple polygon consisting of n vertices and let s, t be a pair of points in P. Let int(P) represent the interior of P and let P¯ represent the exterior of P, i.e. int(P)=P\∂(P) and P¯=R2\int(P). For an integer k≥0, we define a k-violation path from s to t to be a path connecting s and t such that its intersection with P¯ consists of at most k segments. There is no restriction in terms of the number of segments of the path within P. The objective is to compute a path of minimum Euclidean length among all possible (≤k)-violation paths from s to t. In this paper, we study this problem for k=1 and propose an algorithm that computes the shortest one-violation path in O(n3) time. We show that for rectilinear polygons, the minimum length rectilinear one-violation path can be computed in O(nlogn) time. We extend the concept of one-violation path to a one-stretch violation path. In this case, the path between s and t is composed of (a) a path in P from s to a vertex u of P, (b) a path in P¯ between u and a vertex v of P, and (c) a path in P between v and t. We show that a minimum length one-stretch violation path can be computed in O(nlognloglogn) time. Next, we introduce one- and two-violation monotone rectilinear path problems among a set of n disjoint axis-parallel rectangular objects. Let s, t be two points in R2 that are not in the interior of any of the objects. In the case of one-violation monotone path problem, the desired rectilinear path from s to t consists of horizontal edges that are directed towards the right and vertical edges that are directed upwards, except for at most one edge. Similarly, in the case of a two-violation monotone path problem, all horizontal edges are directed towards the right except at most one and all vertical edges are directed upwards except at most one. Our algorithms for both of these problems run in O(nlogn) time. [ABSTRACT FROM AUTHOR]

In the minimum consistent subset (MCS) problem, a connected simple undirected graph G = (V , E) is given whose each vertex is colored by one of the colors { c 1 , c 2 , ... , c k } , and the objective is to compute a minimum size subset C ⊆ V such that for each vertex v ∈ V , its set of nearest neighbors in C (with respect to the hop-distance) contains at least one vertex of the same color as v. The decision version of the MCS problem is NP-complete for general graphs. Even for planar graphs, the problem remains NP-complete. We will consider some simple graph classes like path, spider, caterpillar and comb; and present polynomial-time algorithms. [ABSTRACT FROM AUTHOR]

We study a space-efficient algorithm for computing a centerpoint for a set P of n points in R 2 , where the points in P are given in a read-only array. We propose an algorithm that finds a centerpoint of P in O ( T ( n 2 ) log 3 ⁡ n ) time using O ( S ( n 2 ) ) extra space, where T ( n ) and S ( n ) are the time and extra space complexities of computing the median among a set of n elements stored in a read-only array. We also present the applications of this algorithm for computing the Tukey depth and k -hull of a point set in R 2 . [ABSTRACT FROM AUTHOR]

We study geometric variations of the discriminating code problem. In the discrete version of the problem, a finite set of points P and a finite set of objects S are given in R d . The objective is to choose a subset S ∗ ⊆ S of minimum cardinality such that for each point p i ∈ P , the subset S i ∗ ⊆ S ∗ covering p i satisfies S i ∗ ≠ ∅ , and each pair p i , p j ∈ P , i ≠ j , we have S i ∗ ≠ S j ∗ . In the continuous version of the problem, the solution set S ∗ can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case ( d = 1 ), the points in P are placed on a horizontal line L, and the objects in S are finite-length line segments aligned with L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in one dimension. Still for the 1-dimensional discrete version, we design a polynomial-time 2-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case ( d = 2 ) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce (16 · O P T + 1) -approximate and (64 · O P T + 1) -approximate solutions respectively, using rounding of suitably defined integer linear programming problems. Finally, we apply our techniques to a related variant of the discrete problem, where instead of points and geometric objects we just have a set S of objects. The goal is to select a small subset S ∗ of objects so that all objects of S are discriminated by their intersection with the objects of S ∗ . This problem can be viewed as a graph problem by stating it in terms of the vertices of the geometric intersection graph of S. Under this graph-theoretical form, it is known as the identifying code problem. We show that the identifying code problem for axis-parallel unit square intersection graphs (in d = 2 ) can be solved in the same manner as for the discrete version of the discriminating code problem for unit square objects described above, and all our positive approximation results still hold in this setting. [ABSTRACT FROM AUTHOR]

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 the 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: • computing the minimum enclosing circle (MEC) of a set of n points in R 2 , and • linear programming problems with two and three variables and n constraints. 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. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of designing in-place algorithms for finding the maximum clique in the intersection graphs of axis-parallel rectangles and disks in R 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 + n K ) , 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. [ABSTRACT FROM AUTHOR]

Algorithms and Discrete Mathematics - celebrating the silver jubilee of IITG Guwahati. [Extracted from the article]

Let P be a set of n points, where each point is colored with one of the k possible colors. We present efficient algorithms to preprocess P such that for a given query point q , we can quickly identify the smallest color spanning object of the desired type containing q. In this paper, we focus on (i) intervals, (ii) axis-parallel square, (i i i) axis-parallel rectangle, (i v) equilateral triangle of fixed orientation and (v) circle, as our desired type of objects. [ABSTRACT FROM AUTHOR]

Classical 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 P = P r ∪ P b in R 2 and R 3 , where P r and P b represent a set of n red points and a set of m 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 R 2 , and (ii) an axis-parallel monochromatic cuboid of maximum size in R 3. The time complexities of the algorithms for problems (i) and (ii) are O (m (m + n) (m n + m log m + n log n)) and O (m 3 n + m 2 n log n) , 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 k -d tree for a set of n points in R k supports orthogonal range counting query using O (1) extra workspace, and with O (n 1 − 1 ∕ k) query time complexity. The construction time of this data structure is O (n log n). Both the construction and query algorithms are non-recursive in nature that do not need O (log n) size recursion stack compared to the previously known construction algorithm for in-place k -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 P = P r ∪ P b , where each point in P b (resp. P r) is associated with a negative (resp. positive) real-valued weight that runs in O (m 2 (n + m) log (n + m)) time using O (n) extra space. [ABSTRACT FROM AUTHOR]

In this paper, we study some fundamental facility location problems from the space-efficient perspective. We show that 1-center problem in Euclidean space and in tree networks can be efficiently solved in constant-workspace model. We use a virtual pairing tree during the pruning stage that allows the maintenance of pruned elements. We also show that a feasible region during the prune-and-search process can always be maintained using O (1) space. These results realize the solutions to the problems in constant work-space model: linear programming in 2-d, 3-d, 2-center in trees, and largest disk inside a convex polygon. [ABSTRACT FROM AUTHOR]

In this paper, we study the Shortest Color Spanning t - Intervals problem, and related generalizations, namely Smallest Color Spanning t - Squares and Smallest Color Spanning t - Circles. The generic setting is the following: we are given n points in the plane (or on a line), each colored with one of k colors. For each color i we also have a demand s i. Given a budget t , we are required to find at most t objects (for example, intervals, squares, circles, etc.) that cover at least s i points of color i. Typically, the goal is to minimize the maximum perimeter or area. We provide exact algorithms for these problems for the cases of intervals, circles and squares, generalizing several known results. In the case of intervals, we provide a comprehensive understanding of the complexity landscape of the problem after taking several natural parameters into account. Given that the problem turns out to be W 1 -hard parameterized by the standard parameters, we introduce a new parameter, namely sparsity, and prove new hardness and tractability results in this context. For squares and circles, we use existing algorithms of one smallest color spanning object in order to design algorithms for getting t identical objects of minimum size whose union spans all the colors. [ABSTRACT FROM AUTHOR]

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. The problem remains open since 2002, as mentioned in a lecture slide of David Eppstein. In this paper, we have performed an exhaustive study on the problem. We show that, if the points are placed in R 2 then the problem is NP-hard even for simplest type of covering objects like disks or squares. In contrast, Eppstein (2017) [10] proposed a polynomial time algorithm for maximizing the sum of radii (or perimeter) of non-overlapping disks when the points are arbitrarily placed in R 2. We show that Eppstein's algorithm for maximizing sum of perimeter of the disks in R 2 gives a 2-approximation solution for the sum of area maximization problem. We also propose a PTAS for the same problem. Our results can be extended in higher dimensions as well as for a class of centrally symmetric convex objects. [ABSTRACT FROM AUTHOR]

Highlights • Algorithms for covering and hitting a given set of line segments by two congruent squares of minimum size is studied. • The algorithm produces optimum solution by sequentially reading the input array (read only) twice. • The extra space complexity of the algorithm is O (1). • A restricted version of covering is also studied where each object is to be completely covered by at least one square. • This algorithm gives 2 approximation result to cover/hit the segments with two congruent disks of minimum size. Abstract This paper discusses the problem of covering and hitting a set of line segments L in R 2 by a pair of axis-parallel congruent squares of minimum size. We also discuss the restricted version of covering, where each line segment in L is to be covered completely by at least one square. The proposed algorithms assume that the input segments are given in a read-only array. For each of these problems (i.e. covering , hitting and restricted covering problems), our proposed algorithm reports the optimum result by executing only two passes of reading the input array sequentially. All these algorithms need only O (1) extra space. The solution of these problems also give a 2 approximation for covering and hitting those line segments L by two congruent disks of minimum radius with same computational complexity. [ABSTRACT FROM AUTHOR]

Sample preparation is a fundamental preprocessing step needed in almost all biochemical assays and is conveniently automated on a microfluidic lab-on-chip. In digital microfluidics, it is accomplished by a sequence of droplet-mix-split steps on a biochip. Many real-life applications require a sample with multiple concentration factors (CFs). Existing algorithms, while producing multi-CF targets, attempt to share the mix-split steps in order to reduce reactant-cost and sample-preparation time. However, all prior approaches have two limitations: 1) sharing of intermediate droplets can be best effected only when all required target CFs are known a priori and 2) the processing time may vary depending on the allowable error-tolerance in target-CFs. In this paper, we present a cost-effective solution to multi-CF-dilution on-demand, by using only one (or two) mix-split step(s). In order to service dynamically arriving requests of multiple CFs quickly, we prepare dilutions of the sample with a few CFs in advance (called source-CFs), and fill on-chip reservoirs with these fluids. For minimizing the number of such preprocessed CFs, we present an integer linear programming-based method, an approximation algorithm, and a heuristic algorithm. The proposed methods also allow the users to tradeoff the number of on-chip reservoirs against service time for various applications. Simulation results for several target sets demonstrate the superiority of the proposed techniques over prior art in terms of the number of mix-split steps, waste droplets, and reactant usage when the on-chip reservoirs are preloaded with source-CFs using a customized droplet-streaming engine. [ABSTRACT FROM AUTHOR]

In the acrophobic guard watchtower problem for a polyhedral terrain, a square axis-aligned platform is placed on the top of a tower whose bottom end-point lies on the surface of the terrain. As in the standard watchtower problem, the objective is to minimize the height (i.e., the length) of the watchtower such that every point on the surface of the terrain is weakly visible from the platform placed on the top of the tower. In this paper, we show that in R 2 the problem can be solved in O (n) time, and in R 3 it takes O (n log ⁡ n) time, where n is the total number of vertices of the terrain. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in general position in the plane which is partitioned into color classes. The set P is said to be color-balanced if the number of points of each color is at most [n/2] . Given a color-balanced point set P, a balanced cut is a line which partitions P into two color-balanced point sets, each of size at most 2n/3+1 . A colored matching of P is a perfect matching in which every edge connects two points of distinct colors by a straight line segment. A plane colored matching is a colored matching which is non-crossing. In this paper, we present an algorithm which computes a balanced cut for P in linear time. Consequently, we present an algorithm which computes a plane colored matching of P optimally in Θ(nlog n) time. [ABSTRACT FROM AUTHOR]

Given a convex polygon with n vertices, we study the problem of identifying a triangle with its smallest side as large as possible among all the triangles that can be drawn inside the polygon. We show that at least one of the vertices of such a triangle must coincide with a vertex of the polygon. We also propose an O (n 2) time algorithm to compute such a triangle inside the given convex polygon. [ABSTRACT FROM AUTHOR]

In the paper "Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares", Theor. Comput. Sci. 769 (2019) 63–74, the LHIT problem is proposed as follows: For a given set of non-intersecting line segments L = { ℓ 1 , ℓ 2 , ... , ℓ n } in Image 1 , compute two axis-parallel congruent squares S 1 and S 2 of minimum size whose union hits all the line segments in L , and a linear time algorithm was proposed. Later it was observed that the algorithm has a bug. In this corrigendum, we corrected the algorithm. The time complexity of the corrected algorithm is O (n 2). [ABSTRACT FROM AUTHOR]

A new type of range searching problem, called the partial enclosure range searching problem, is introduced in this paper. Given a set of geometric objects S and a query region Q , our goal is to identify those objects in S which intersect the query region Q by at least a fixed proportion of their original size. Two variations of this problem are studied. In the first variation, the objects in S are axis-parallel line segments and the goal is to count the total number of members of S so that their intersection with Q is at least a given proportion of their size. Here, Q can be an axis-parallel rectangle or a parallelogram of arbitrary orientation. In the second variation, S is a polygon and Q is an axis-parallel rectangle. The problem is to report the area of the intersection between the polygon S and a query rectangle Q. [ABSTRACT FROM AUTHOR]

In this paper, we consider the dynamic version of covering the convex hull of a point set P in R2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2ropt at any query time, where ropt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O (log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2. [ABSTRACT FROM AUTHOR]

We study the rectilinear path problem in the presence of disjoint axis parallel rectangular obstacles in the read-only and in-place setup. The input to the problem is a set R of n axis-parallel rectangular obstacles in R 2 . The objective is to answer the following query efficiently. Path-Query ( p , q ) : Given a pair of points p and q , report an axis-parallel path from p to q avoiding the obstacles in R . In the read-only setup, we show that Path-Query ( p , q ) problem can be solved in O ( n 2 s + n log s ) time using O ( s ) extra space. We also show that the existence of an x -monotone path and reporting it, if it exists, can be done with the same asymptotic time complexity. If the objective is to test the existence of an x y -monotone path between the given pair of points p and q avoiding the obstacles, and report it if exists, then our proposed algorithm needs O ( n 2 s + n log s + M s log n ) time with O ( s ) extra space, where M s is the time complexity for computing the median of n elements in the read-only setup using O ( s ) extra space. Finally, we show that when the obstacles are unit squares instead of rectangles of arbitrary size, then there always exists a path of O ( n ) links between a pair of query points, and the path can be reported in O ( n n ) time using O ( 1 ) extra work-space. It is also shown that there is an instance where the minimum number of links in a path between a pair of specified points is O ( n ) . The objective of the Path-Query ( p , q ) in the in-place setup is to preprocess the input rectangles in a data structure in the input array itself such that for any pair of query points p and q , a rectilinear path can be reported efficiently. Here we propose an algorithm with O ( n log n ) preprocessing time and O ( n 3 / 4 + χ ) query time, where χ is the number of links (bends) in the path. Both the preprocessing and query answering need O ( 1 ) extra space. [ABSTRACT FROM AUTHOR]

In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set of unit disks in . We first present a simple time 5-factor approximation algorithm for this problem, where is the size of the output. The best known 4-factor and 3-factor approximation algorithms for the same problem run in time and respectively [M. De, G. K. Das, P. Carmi and S. C. Nandy, Approximation algorithms for a variant of discrete piercing set problem for unit disks, Int. J. of Computational Geometry and Appl., 22(6):461-477, 2013]. We show that the time complexity of the in-place 4-factor approximation algorithm for this problem can be improved to . A minor modification of this algorithm produces a -factor approximation algorithm in time. The same techniques can be applied to have a 3-factor and a -factor approximation algorithms in time and respectively. Finally, we propose a very important shifting lemma, which is of independent interest, and it helps to present -factor approximation algorithm for the same problem. It also helps to improve the time complexity of the proposed PTAS for the problem. [ABSTRACT FROM AUTHOR]

Abstract: The coverage problem in wireless sensor networks addresses the problem of covering a region with sensors. Many different definitions of coverage are there in the literature depending on the goal of the coverage. In this paper, we address the problem of determining the quality of a sensor deployment against an intruder who can walk along a straight line. A line segment is said to be k-covered if it intersects the sensing regions of at least sensors distributed in . Similarly, it is said to be k-uncovered if it intersects the sensing regions, that is assumed to be circular, of at most sensors. We introduce two new metrics, smallest -covered line segment and longest -uncovered line segment, for measuring the quality of line coverage achieved by a sensor deployment. The intruder can walk a distance less than the smallest -covered line segment without ever being detected by sensors. So, this metric gives an estimate on the distance an intruder can walk in a straight line path before being detected by sensors. On the other side, the defender would want to deploy sensors so that the length of the longest -uncovered line segment is minimized. Given a deployment of sensors, we propose deterministic algorithms to determine the smallest -covered line segment and longest -uncovered line segment where the line segments can be of the following types: (i) axis-parallel (horizontal and vertical) line segments, (ii) line segments whose one endpoint is fixed and is of arbitrary orientation and (iii) arbitrary line segments. The time complexities for the first and second types of line segments are for both smallest -covered line segment and longest -uncovered line segment, where is the number of intersections among circles. For the arbitrary line segment case, the smallest -covered segment can be determined in time, whereas, the longest -uncovered segment can be determined in time, where and is a small value greater than or equal to . All our algorithms take linear space. [Copyright &y& Elsevier]