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]

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]

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]

A VLSI chip is fabricated by integrating several rectangular circuit blocks on a 2D silicon floor. The circuit blocks are assumed to be placed isothetically and the netlist attached to each block is given. For wire routing, the terminals belonging to the same net are to be electrically interconnected using conducting paths. A staircase channel is an empty polygonal region on the silicon floor bounded by two monotonically increasing (or decreasing) staircase paths from one corner of the floor to its diagonally opposite corner. The staircase paths are defined by the boundaries of the blocks. In this paper, the problem of determining a monotone staircase channel on the floorplan is considered such that the number of distinct nets whose terminals lie on both sides of the channel, is minimized. Two polynomial-time algorithms are presented based on the network flow paradigm. First, the simple two-terminal net model is considered, i.e., each net is assumed to connect exactly two blocks, for which an O(n×k) time algorithm is proposed, where n and k are respectively the number of blocks and nets on the floor. Next, the algorithm is extended to the more realistic case of multi-terminal net problem. The time complexity of the latter algorithm is O((n+k)×T), where T is the total number of terminals attached to all nets in the floorplan. Solutions to these problems are useful in modeling the repeater block placement that arises in interconnect-driven floorplanning for deep-submicron VLSI physical design. It is also an important problem in context to the classical global routing, where channels are used as routing space on silicon. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for identifying a maximal empty-staircase-polygon (MESP) of largest area, among a set of n points on a rectangular floor. A staircase polygon is an isothetic polygon bounded by two monotonically rising (falling) staircases. A monotonically rising staircase is a sequence of alternatingly horizontal and vertical line segments from the bottom-left corner of the floor to its top-right corner such that for every pair of points α=(xα,yα) and β=(xβ,yβ) on the staircase, xα⩽xβ implies yα⩽yβ. A monotonically falling staircase can similarly be defined from the bottom-right corner of the floor to its top-left corner. An empty staircase polygon is a MESP if it is not contained in another larger empty staircase polygon. The problem of recognizing the largest MESP is formulated using permutation graph, and a simple O(n3) time algorithm is proposed. Next, based on certain novel geometric properties of the problem, an improved algorithm is developed that identifies the largest MESP in O(n2) time and space. The algorithm can be easily tailored for identifying the widest MESP in a similar environment. The general problem of locating the largest area/width MESP among a set of isothetic polygonal obstacles, can be solved easily. These geometric optimization problems have several applications to VLSI layout design, robot motion planning, to name a few. [Copyright &y& Elsevier]

We present an algorithm for finding k nearest neighbors of a given query line among a set of n points distributed arbitrarily on a two-dimensional plane. Our algorithm requires O(n2) time and O(n2/log n) space to preprocess the given set of points, and it answers the query for a given line in O(k+log n) time, where k may also be an input at the query time. Almost a similar technique works for finding k farthest neighbors of a query line, keeping the time and space complexities invariant. We also show that if k is known at the time of preprocessing, the time and space complexities for the preprocessing can be reduced keeping the query times unchanged. [Copyright &y& Elsevier]

In this paper, we propose an algorithm for shattering a set of disjoint line segments of arbitrary length and orientation placed arbitrarily on a 2D plane. The time and space complexities of our algorithm are O(n2) and O(n), respectively. It is an improvement over the O(n2 log n) time algorithm proposed in (R. Freimer, J.S.B. Mitchell, C.D. Piatko, On the complexity of shattering using arrangements, Canadian Conference on Computational Geometry, 1990, pp. 218–222.). A minor modification of this algorithm applies when objects are simple polygons, keeping the time and space complexities invariant. [Copyright &y& Elsevier]

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]

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]

Abstract: One of the classic data structures for storing point sets in 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 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 in time with extra space, where m is the total number of maximal empty rectangles. [Copyright &y& Elsevier]

Abstract: In this paper, two variations of the minimum cost homogeneous range assignment problem for 2-hop broadcast from a given source are considered. A set of radio stations are pre-placed in , and a source station (say) is marked. In our first problem, the objective is to find a real number r such that 2-hop homogeneous broadcast from is possible with range r, and the total power consumption of the entire network is minimum. In the second problem, a real number r is given and the objective is to identify the smallest subset of S for which range r can be assigned to accomplish the 2-hop broadcast from , provided such an assignment is possible. The first problem is solved in time and space. For the second problem, a 2-factor approximation algorithm is proposed that runs in time and space. [Copyright &y& Elsevier]

Abstract: Given a polyhedral terrain with n vertices, the shortest monotone descent path problem deals with finding the shortest path between a pair of points, called source (s) and destination (t) such that the path is constrained to lie on the surface of the terrain, and for every pair of points and on the path, if then , where denotes the distance of p from s along the aforesaid path. This is posed as an open problem by Berg and Kreveld [M. de Berg, M. van Kreveld, Trekking in the Alps without freezing or getting tired, Algorithmica 18 (1997) 306–323]. We show that for some restricted classes of polyhedral terrain, the optimal path can be identified in polynomial time. [Copyright &y& Elsevier]

Abstract: In the context of mobile communication, an efficient algorithm for the base-station placement problem is developed in this paper. The objective is to place a given number of base-stations in a given convex region, and to assign range to each of them such that every point in the region is covered by at least one base-station, and the maximum range assigned is minimized. It is basically covering a region by a given number of equal radius circles where the objective is to minimize the radius. We develop an efficient algorithm for this problem using Voronoi diagram which works for covering a convex region of arbitrary shape. Existing results for this problem are available when the region is a square [K.J. Nurmela, P.R.J. Ostergard, Covering a square with up to 30 equal circles, Research Report HUT-TCS-A62, Laboratory for Theoretical Computer Science, Helsinky University of Technology, 2000] and an equilateral triangle [K.J. Nurmela, Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles, Exp. Math. 9 (2) (2000)]. The minimum radius obtained by our method favorably compares with the results presented in [K.J. Nurmela, P.R.J. Ostergard, Covering a square with up to 30 equal circles, Research Report HUT-TCS-A62, Laboratory for Theoretical Computer Science, Helsinky University of Technology, 2000; K.J. Nurmela, Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles, Exp. Math. 9 (2) (2000)]. But the execution time of our algorithm is a fraction of a second, whereas the existing methods may even take about two weeks’ time for a reasonable value of the number of circles () as reported in [K.J. Nurmela, P.R.J. Ostergard, Covering a square with up to 30 equal circles, Research Report HUT-TCS-A62, Laboratory for Theoretical Computer Science, Helsinky University of Technology, 2000; K.J. Nurmela, Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles, Exp. Math. 9 (2) (2000)]. [Copyright &y& Elsevier]

Abstract: Given a set S of n radio-stations located on a d-dimensional space, a source node s and an integer h , the h-hop broadcast range assignment problem deals with assigning ranges to the members in S so that s can communicate with all other members in S in at most h-hops, and the total power consumption is minimum. The problem is known to be NP-hard for . We propose an time algorithm for the one dimensional version () of the problem. This is an improvement over the existing result on this problem by a factor of h [A.E.F. Clementi et al. The minimum broadcast range assignment problem on linear multi-hop wireless networks, Theoret. Comput. Sci. 299 (2003) 751–761]. [Copyright &y& Elsevier]

We present an efficient algorithm for finding k nearest neighbors of a query line segment among a set of points distributed arbitrarily on a two dimensional plane. Along the way to finding this algorithm, we have obtained an improved triangular range searching technique in 2D. Given a set of n points, we preprocess them to create a data structure using O(n2) time and space, such that given a triangular query region Δ, the number of points inside Δ can be reported in O(logn) time. Finally, this triangular range counting technique is used for finding k nearest neighbors of a query straight line segment in O(log2n+k) time. [Copyright &y& Elsevier]

Let S be a collection of geometric objects in R 3, and let P be another geometric object in R 3. The free configuration space of P with respect to S is the set of all possible placements of P so that P does not intersect the set S. Finding combinatorial and computational bounds for the computation of the free configuration space is a currently active area of research in computational geometry. We show in this paper that the free configuration space of a convex polyhedron P freely translating over a polyhedral terrain having a convex projection T can be computed in O(nm+k+t) time in the worst case, where m and n are the number of faces of P and T, respectively, k denotes the size of the output and t is a parameter whose value could be, at most, O(n2mlogn). [Copyright &y& Elsevier]

Focuses on solving the geometric bipartitioning of a point set and area-balanced staircase bipartitioning of a very large scale integrated circuits floor plan using the heuristic search algorithms. Formulations of graph search problems; Comparison between the proposed depth-first approach and the Complete Karmarkar-Karp algorithm.

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]

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]

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]

Abstract: In this paper we study the diffuse reflection diameter and diffuse reflection radius problems for convex-quadrilateralizable polygons. In the usual model of diffuse reflection, a light ray incident at a point on the reflecting surface is reflected from that point in all possible inward directions. A ray reflected from a polygonal edge may graze that reflecting edge but an incident ray cannot graze the reflecting edge. The diffuse reflection diameter of a simple polygon is the minimum number of diffuse reflections that may be needed in the worst case to illuminate any target point from any point light source inside . We show that the diameter is upper bounded by in our usual model of diffuse reflection for convex-quadrilateralizable polygons. To the best of our knowledge, this is the first upper bound on diffuse reflection diameter within a fraction of for such a class of polygons. We also show that the diffuse reflection radius of a convex-quadrilateralizable simple polygon with vertices is at most under the usual model of diffuse reflection. In other words, there exists a point inside such a polygon from which usual diffuse reflections are always sufficient to illuminate the entire polygon. In order to establish these bounds for the usual model, we first show that the diameter and radius are and respectively, for the same class of polygons for a relaxed model of diffuse reflections; in the relaxed model an incident ray is permitted to graze a reflecting edge before turning and reflecting off the same edge at any interior point on that edge. We also show that the worst-case diameter and radius lower bounds of and respectively, are sometimes attained in the usual model, as well as in the relaxed model of diffuse reflection. [Copyright &y& Elsevier]

Abstract: In this paper, we will study the problem of locating the center of the smallest enclosing circle of a set P of n points, where the center is constrained to lie on a query line segment. The preprocessing time and space complexities of our proposed algorithm are and respectively; the query time complexity is . [Copyright &y& Elsevier]