Search

We propose algorithms to compute the Minkowski sum of two or more convex polytopes represented by their face lattices in R d. The time and space complexities of the pair-wise algorithm are O (d ω n m) and O (n + m + M) , respectively, where n , m and M are the face lattice sizes of the two summands and the sum, respectively, and ω ≈ 2. 37 , currently, is the matrix multiplication exponent. We also show that this algorithm is worst-case optimal for fixed d. Next, we generalize the pair-wise algorithm to r > 2 convex polytopes in R d. The time and space complexities of the r -summands generalized algorithm are O (d ω min { M N , r + ∏ i = 1 r N i }) and O (M + N) , respectively, where N i , 1 ≤ i ≤ r , is the size of i th summand, N = ∑ i = 1 r N i is the total input size and M is the output size of the Minkowski sum. We show that the r -summands generalized algorithm is worst-case optimal for fixed d ≥ 3 and r < d. [ABSTRACT FROM AUTHOR]

We present a linear time algorithm for the weighted k -center problem on trees for fixed k. This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O (n log ⁡ n) by Wang et al. (2018) [20]. Whether an O (n) time algorithm exists for arbitrary k is still open. [ABSTRACT FROM AUTHOR]

In this paper we present efficient algorithms to compute the radius, diameter, incenter, circumcenter, width and k dimensional enclosing cylinder for convex polyhedral and convex polyhedral offset distance functions in plane and in ℜ d for several types of inputs. We get optimal algorithms when the time complexities are linear. Let the size of input (convex polyhedron P /set S of points/convex polyhedra) be n / N , respectively, size of distance function convex polygon/polyhedron Q be m and size of constraint convex polyhedral region R be r in plane or ℜ d. The radius, incenter and circumcenter of the convex polygon P in ℜ 2 can be optimally computed in linear time, i.e. O (n + m) and in time O (n + m + r) , if the incenter or circumcenter is additionally constrained in a convex polygon/polyhedron R. In ℜ d , the radius, incenter and circumcenter of a convex polyhedron as well as of a set of convex polyhedra, unconstrained or constrained, can be computed in O (N m) and O (N m + r) time respectively, for convex constraint polyhedral region R. We also compute the minimum stabbing sphere for a set of convex polyhedra, unconstrained or constrained, for the above mentioned distance functions in O (N m) -time or O (N m + r) -time respectively for convex constraint polyhedral region R in ℜ d. The diameter of a convex polygon in plane can be computed in O (n + m) time and the diameter of a convex polyhedron in ℜ d can be computed in O (n m) time. The width of a convex polyhedron can be computed in O (n + m) time and O (n 2 m) time, for ℜ 2 and ℜ d , respectively. The diameter and width of a set of convex polyhedra can be computed in O (N m) -time and (N 2 m) , respectively, in any dimensions. We also show how the k dimensional minimum enclosing/stabbing cylinder for the convex polyhedron P can be computed in O (n d − k + 2 m 2) in ℜ d and in O (n d m (n + m)) in ℜ d for k = 1. The k dimensional minimum enclosing/stabbing cylinder for the set of convex polyhedra S in ℜ d can be computed in O (N d − k + 2 m 2) -time. The diameter and width problems can also be solved for a set of points in ℜ d , either in time O (n m) or in time O (m T (n)) , where T (n) is the time complexity of the best convex hull computation algorithm for the given set of points. [ABSTRACT FROM AUTHOR]

This work proposes an efficient identification scheme for simultaneous input and parameter estimation of the hysteretic systems. For this purpose, a quasi-Monte Carlo (QMC)-simulation-based approach is adopted, where the sigma point generation scheme is coupled with a minimum variance unbiased estimator. In this process, additional bounds and constraints on the parameters are introduced to control the stability and convergence. The accuracy of the proposed algorithm is validated using a synthetic experiment on a frame whose nonlinear behavior is characterized by the Bouc–Wen–Baber–Noori model, that is, with degradation and pinching. Once the proposed algorithm is validated, its performance is further demonstrated using the shake table test of a full-scale bridge pier. The identified parameters in this case are utilized for damage quantification using a modified Park and Ang damage index. Overall, this study shows the robustness of the proposed algorithm for combined input estimation and condition assessment of inelastic reinforced concrete structures with a significant level of accuracy. [ABSTRACT FROM AUTHOR]

Summary: Constraint minimum variance unbiased estimator is improvised for simultaneous input and parameter estimation of the Bouc–Wen hysteretic system of a full‐scale bridge pier. The essential structural properties in this case (i.e., bounded input and bounded output) are incorporated in the form of constraint conditions along with degradation and pinching effects. To demonstrate the efficiency of this algorithm, two different types of sigma points generation schemes (viz., unscented transformed points and cubature quadrature points) are presented here. First, the algorithm is validated using simulated response obtained from a single‐bay single‐storey reinforced concrete frame, whose hysteretic parameters are obtained by minimizing the error between the model and experimentally observed load‐deformation characteristics. The rationale behind the use of experimentally observed hysteresis in simulation is to replicate the actual structure so that the realistic material behaviour is maintained. Once the algorithm is validated, its performance is further demonstrated using experimental results of a full‐scale bridge pier, which is the main objective of this study. The numerical results presented in this paper clearly show the robustness of the proposed algorithm using unscented sigma points, which can identify both hysteretic properties and input excitation with sufficient level of accuracy. [ABSTRACT FROM AUTHOR]

We solve a movement problem in which there are n sensors in path network in plane, where any sensor communicates only with its two immediate neighbors and only at a given maximum communication distance λ. Initially, some of the inter-sensor distances may be more than λ. We need to move sensors so that each sensor is in the communication range of its two neighbors, keeping the path topology intact. The problem is to minimize the maximum movement of any sensor. We present an O (n 3) -time algorithm to compute the new positions of sensors to establish transmission connectivity, called λ -connectivity in the paper, in a convex path-network which minimizes the maximum movement among the sensors. We also generalize our algorithm for ring, non-convex path, tethered and heterogeneous networks. [ABSTRACT FROM AUTHOR]

We provide constant factor approximation algorithms for the Minimum Dominating Set (MDS) problem on several subclasses of string graphs i.e. intersection graphs of simple curves on the plane. For k ≥ 0 , unit B k -VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends) and each segment of the curve being unit length. We give an 18-approximation algorithm for the MDS problem on unit B 0 -VPG graphs. This partially addresses a question of Katz et al. (2005) [24]. We also give an O (k 4) -approximation algorithm for the MDS problem on unit B k -VPG graphs. We show that there is an 8-approximation algorithm for the MDS problem on vertically-stabbed L -graphs. We also give a 656-approximation algorithm for the MDS problem on stabbed rectangle overlap graphs. This is the first constant-factor approximation algorithm for the MDS problem on stabbed rectangle overlap graphs and extends a result of Bandyapadhyay et al. (2019) [31]. We prove some hardness results to complement the above results. [ABSTRACT FROM AUTHOR]

Let be a set of input points in the plane. An algorithm is proposed to place a pair of axis-parallel unit squares, either intersecting with no points in the intersection zone or disjoint, together enclosing the maximum number of input points. The time and space complexities of the algorithm are both . In case the input points are allowed to lie inside the intersection zone of two intersecting axis-parallel unit squares, two such unit squares enclosing the maximum number of input points can be placed in time using space. [ABSTRACT FROM AUTHOR]

Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoretical guarantee on its quality. The other one considers placement as a graph-embedding problem and designs approximation algorithms with provable bounds on the quality of the solution. In this article, we aim at unifying the above two directions. First, we extend the existing approximation algorithms for graph embedding in 1D and 2D grid to those for hypergraphs, which typically model circuits to be placed on a FPGA. We prove an approximation bound of O(d√log nlog log n) for 1D, that is, linear arrangement and O(d log nlog log n) for the 2D grid, where d is the maximum degree of hyperedges and n, the number of vertices in the hypergraph. Next, we propose an efficient method based on linear arrangement of the CLBs and the notion of space-filling curves for placing the configurable logic blocks (CLBs) of a netlist on island-style FPGAs with an approximation guarantee of O( ∜log n√kd log log n), where k is the number of nets. For the set of FPGA placement benchmarks, the running time is near linear in the number of CLBs thus allowing for scalability towards large circuits. We obtained a 33x speed-up, on average, with only 1.31x degradation in the quality of the solution compared to that produced by the popular FPGA tool VPR, thereby demonstrating the suitability of this very fast method for FPGA placement, with a provable performance guarantee. [ABSTRACT FROM AUTHOR]

Given a set of n colored points in IR2 with a total of m (3 ≤ m ≤ n) colors, the problem of identifying the smallest color-spanning object of some predefined shape is studied in this paper. We shall consider two different shapes: (i) corridor and (ii) rectangle of arbitrary orientation. Our proposed algorithm for identifying the smallest color-spanning corridor is simple and runs in O(n2log n) time using O(n) space. A dynamic version of the problem is also studied, where new points may be added, and the narrowest color-spanning corridor at any instance can be reported in O(mn(α(n))2log m) time. Our algorithm for identifying the smallest color-spanning rectangle of arbitrary orientation runs in O(n3log m) time and O(n) space. [ABSTRACT FROM AUTHOR]

Two points a and b are said to be L-visible among a set of polygonal obstacles if the length of the shortest path from a to b avoiding these obstacles is no more than L. For a given convex polygon P with n vertices, Gewali et al.1 addressed the guard placement problem on the boundary of P that covers the maximum area outside to the polygon under L-visibility with P as obstacle. Their proposed algorithm runs in O(n) time if $L\, < \,{{\pi (P)} \over 2}$, where π(P) denotes the perimeter of P. They conjectured that if $L\, \ge \,{{\pi (P)} \over 2}$, then the problem can be solved in subquadratic time. In this paper, we settle the conjecture in the affirmative sense, by proposing an easy to implement linear time algorithm for any arbitrary value of L. [ABSTRACT FROM AUTHOR]

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: This paper presents simple and deterministic algorithms for partial point set pattern matching in 2D. Given a set P of n points, called sample set, and a query set Q of k points (), the problem is to find a matching of Q with a subset of P under rigid motion. The match may be of two types: exact and approximate. If an exact matching exists, then each point in Q coincides with the corresponding point in P under some translation and/or rotation. For an approximate match, some translation and/or rotation may be allowed such that each point in Q lies in a predefined -neighborhood region around some point in P. The proposed algorithm for the exact matching needs space and preprocessing time. The existence of a match for a given query set Q can be checked in time in the worst-case, where is the maximum number of equidistant pairs of point in P. For a set of n points, may be in the worst-case. Some applications of the partial point set pattern matching are then illustrated. Experimental results on random point sets and some fingerprint databases show that, in practice, the computation time is much smaller than the worst-case requirement. The algorithm is then extended for checking the exact match of a set of k line segments in the query set with a k-subset of n line segments in the sample set under rigid motion in time. Next, a simple version of the approximate matching problem is studied where one point of Q exactly matches with a point of P, and each of the other points of Q lie in the -neighborhood of some point of P. The worst-case time and space complexities of the proposed algorithm are and , respectively. The proposed algorithms will find many applications to fingerprint matching, image registration, and object recognition. [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]

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]

• Proved several lower and upper bounds on the Voronoi games on simple and convex polygons. Almost all are tight. • Devised optimal strategies for the games on convex polygons in poly-log linear and linear time for the players. • Extended the results on the bounds on the Voronoi games on polyhedra in R 3. • Polynomial-time strategies for both the players are devised for Voronoi games on convex polyhedra with restrictions. • Computed common intersection of ellipses in O (n log ⁡ n) time. The competitive facility location problem is the problem of determining facility locations involving multiple players to optimize their various gains. The Voronoi game is a competitive facility location problem on a given arena played by two players, the server and the adversary. The players alternately take turns, one or more times, to place their facilities in the arena with a predetermined set of n clients , where both facilities and clients are denoted by points, to maximize some resource gain. The Voronoi game on a polygon P is a type of competitive facility location problem where n clients are located on the boundary of P. The server, Alice, and adversary, Bob, are respectively in the interior and the exterior of the polygon P at locations A and B , respectively. Additionally, the metrics for Alice and Bob are the internal and external geodesic distances for the polygon P , respectively. In this paper, we present some surprising results on the Voronoi games on polygons. We prove lower and upper bounds of ⌈ n / 3 ⌉ and n − 1 respectively in the single-round game for the number of clients won by the server for n clients. Both bounds are tight. In the process, we show that in some convex polygons, the adversary wins no more than k clients in a k -round Voronoi game for any k ≤ n. Consequentially, the adversary Bob does not have a guaranteed good winning strategy even for the simpler case of convex polygons, i.e., there exist convex polygons such that no placement of B guarantees more than k clients in the k -round game. We also design O (n log 2 ⁡ n + m log ⁡ n) and O (n + m) time algorithms to compute the optimal locations for the server and the adversary respectively to maximize their client counts where the convex polygon has size m. Moreover, we present an O (n log ⁡ n) time algorithm to compute the common intersection of a set of n ellipses. This is needed in our algorithm and may be of independent interest. Lastly, we present some results on the Voronoi games, where the arena is a convex polytope. The server and adversary are respectively in the interior and exterior of P , and the clients are on the polytope boundary. [ABSTRACT FROM AUTHOR]

In this paper we study the last round of the discrete Voronoi game in R2, a problem which is also of independent interest in competitive facility location. The game consists of two players P1 and P2, and a finite set U of users in the plane. The players have already placed two disjoint sets of facilities F and S, respectively, in the plane. The game begins with P1 placing a new facility followed by P2 placing another facility, and the objective of both the players is to maximize their own total payoffs. In this paper we propose polynomial time algorithms for determining the optimal strategies of both the players for arbitrarily located existing facilities F and S. We show that in the L1 and the L∞ metrics, the optimal strategy of P2, given any placement of P1, can be found in O(nlog n) time, and the optimal strategy of P1 can be found in O(n5log n) time. In the L2 metric, the optimal strategies of P2 and P1 can be obtained in O(n2) and O(n8) times, respectively. [ABSTRACT FROM AUTHOR]

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]

Abstract: In this paper we consider an extension of the classical facility location problem where besides n weighted customers, a set of p collection depots are also given. In this setting the service of a customer consists of the travel of a server to the customer and return back to the center via a collection depot. We have analyzed the problem and showed that the collection depots problem using the Euclidean metric can be transformed to number of different classical facility location problems and this bound is tight. We then show the existence of small coresets for these problems. These coresets are then used to provide -factor approximation algorithms which have linear running times for fixed customer weights and ϵ. [Copyright &y& Elsevier]

Abstract: Let P be a polygonal region which is forbidden for placing a base station in the context of mobile communication. Our objective is to place one base station at any point on the boundary of P and assign a range such that every point in the region is covered by that base station and the range assigned to that base station for covering the region is minimum among all such possible choices of base stations. Here we consider the forbidden region P as convex and base station can be placed on the boundary of the region. We present optimum linear time algorithm for that problem. In addition, we propose a linear time algorithm for placing a pair of base stations on a specified side of the boundary such that the range assigned to those base stations in order to cover the region is minimum among all such possible choices of a pair of base stations on that side. [Copyright &y& Elsevier]

This work generalizes the classical problem of finding the largest empty rectangle among obstacles in 2D. Given a set P of n points, here a maximal empty rectangle (MER) is defined as a rectangle of arbitrary orientation such that each of its four boundaries contain at least one member of P and the interior of the rectangle is empty. We propose a very simple algorithm based on standard data structure to locate a MER of largest area in the plane. The worst-case time complexity of our algorithm is O(n3). Though the worst-case space complexity is O(n2), it reserves O(nlogn) space on an average to maintain the required data structure during the execution of the algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we identify a minimum width rectangular annulus that encloses a given set of points in a plane. We propose an time and space algorithm for this problem. To the best of our knowledge this is the first sub-cubic algorithm for a rectangular annulus for arbitrary orientation. [Copyright &y& Elsevier]

The database skyline query (or non-domination query) has a spatial form: Given a set P with n point sites, and a point set S of m locations of interest, a site p ∈ P is a skyline point if and only if for each q ∈ P ∖ { p } , there exists at least one location s ∈ S that is closer to p than to q. We reduce the problem of determining skyline points to the problem of finding sites that have non-empty cells in an additively weighted Voronoi diagram under a convex distance function. The weights of said Voronoi diagram are derived from the coordinates of the sites of P , while the convex distance function is derived from the set of locations S. In the two-dimensional plane, this reduction gives an O ((n + m) log ⁡ (n + m)) -time algorithm to find the skyline points. [ABSTRACT FROM AUTHOR]