We design and engineer FAST-SPARSE-SPANNER, a simple and practical (fast and memory-efficient) algorithm for constructing sparse low stretch factor geometric graphs on large pointsets in the plane. To our knowledge, this is the first practical algorithm to construct fast low stretch factor graphs on large pointsets with average degrees (hence, the number of edges) competitive with that of greedy spanners, the sparsest known class of Euclidean geometric spanners. Although theoretically not guaranteed to produce t-spanners, we always found in our rigorous experiments that FAST-SPARSE-SPANNER generated near-greedy size t-spanners. To evaluate our implementation in terms of computation speed, memory usage, and quality of output, we performed extensive experiments with synthetic and real-world pointsets, and by comparing it to our closest competitor BUCKETING, the fastest known greedy spanner algorithm for pointsets in the plane, devised by Alewijnse et al. (2017) [5]. Our experiment with constructing a 1.1-spanner on a large synthetic pointset with 128K points uniformly distributed within a square shows more than a 41-fold speedup with roughly a third of the memory usage of that of BUCKETING, but with only a 3% increase in the average degree of the resulting graph. When ran on a pointset with a million points drawn from the same distribution, we observed a 130-fold speedup, with roughly a fourth of the memory usage of that of BUCKETING, and just a 6% increase in the average degree. In terms of diameter, the graphs generated by FAST-SPARSE-SPANNER beat greedy spanners in most cases (have substantially lower diameter) while maintaining near-greedy average degree. Further, our algorithm can be easily parallelized to take advantage of parallel environments. We share the implementations via GitHub for broader uses and future research. GitHub repository. https://github.com/ghoshanirban/FSS.

The construction of bounded-degree plane geometric spanners has been a focus of interest since 2002 when Bose, Gudmundsson, and Smid proposed the first algorithm to construct such spanners. To date, 11 algorithms have been designed with various tradeoffs in degree and stretch-factor. We have implemented these sophisticated spanner algorithms in C++ using the CGAL library and experimented with them using large synthetic and real-world pointsets. Our experiments have revealed their practical behavior and real-world efficacy. We share the implementations via GitHub for broader uses and future research.We design and engineer EstimateStretchFactor, a simple practical algorithm, which can estimate stretch-factors (obtains lower bounds on the exact stretch-factors) of geometric spanners - a challenging problem for which no practical algorithm is known yet. In our experiments with bounded-degree plane geometric spanners, we found that EstimateStretchFactor estimated stretch-factors almost precisely. Further, it gave linear runtime performance in practice for the pointset distributions considered in this work, making it much faster than the naive Dijkstra-based algorithm for calculating stretch-factors.

Given a set of n points in the plane, the Unit Disk Cover (UDC) problem asks to compute the minimum number of unit disks required to cover the points, along with a placement of the disks. The problem is NP-hard and several approximation algorithms have been designed over the last three decades. In this paper, we have engineered and experimentally compared practical performances of some of these algorithms on massive pointsets. The goal is to investigate which algorithms run fast and give good approximation in practice. We present a simple 7-approximation algorithm for UDC that runs in O(n) expected time and uses O(s) extra space, where s denotes the size of the generated cover. In our experiments, it turned out to be the speediest of all. We also present two heuristics to reduce the sizes of covers generated by it without slowing it down by much. To our knowledge, this is the first work that experimentally compares algorithms for the UDC problem. Experiments with them using massive pointsets (in the order of millions) throw light on their practical uses. We share the engineered algorithms via GitHub1 for broader uses and future research in the domain of geometric optimization.

Introduced by Callahan and Kosaraju back in 1995, the concept of well-separated pair decomposition (WSPD) has occupied a special significance in computational geometry when it comes to solving distance problems in d-space. We present an in-browser tool that can be used to visualize WSPDs and several of their applications in 2-space. Apart from research, it can also be used by instructors for introducing WSPDs in a classroom setting. The tool will be permanently maintained by the third author at https://wisno33.github.io/VisualizingWSPDsAndTheirApplications/.

A unit disk graph G on a given set P of points in the plane is a geometric graph where an edge exists between two points p,q∈P if and only if |pq|≤1. A spanning subgraph G′ of G is a k-hop spanner if and only if for every edge pq∈G, there is a path between p,q in G′ with at most k edges. We obtain the following results for unit disk graphs in the plane. (i) Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n. (ii) Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges. (iii) Every n-vertex unit disk graph has a 2-hop spanner with O(nlog⁡n) edges. This is the first nontrivial construction of 2-hop spanners. (iv) For every sufficiently large positive integer n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. Previously, no lower bound greater than 2 was known. (v) For every finite point set on a circle, there exists a plane (i.e., crossing-free) 4-hop spanner. As such, this provides a tight bound for points on a circle. (vi) The maximum degree of k-hop spanners cannot be bounded from above by a function of k for any positive integer k.

We study a coverage and tour planning problem wherein a robot with limited sensor coverage is assigned to serve n known points in an environment. A location is served if it is within the visibility range of the robot's sensor. However, the robot is equipped with a battery that powers the robot to travel a maximum distance of B. Several charging stations are placed in the environment so that the robot can charge itself (if needed) to complete the mission. The objective is to compute an energy-constrained tour that starts at a given start location, visits a minimum set of service locations for serving the n points of interest, and returns to the start location. We also aim to minimize the distance traveled between any two consecutive service locations in the tour via a subset of charging stations. This problem has applications in search-and-rescue and surveillance missions where such coverage and energy-aware path planning are of utmost importance. We propose a new algorithm for this problem and show its efficacy using experiments with up to 1000 points of interest on a plane. The running time of our algorithm for such a scenario was a negligible 5.33 sec.

The construction of bounded-degree plane geometric spanners has been a focus of interest in the field of geometric spanners for a long time. To date, several algorithms have been designed with various trade-offs in degree and stretch factor. Using JSXGraph, a state-of-the-art JavaScript library for geometry, we have implemented seven of these sophisticated algorithms so that they can be used for further research and teaching computational geometry. We believe that our interactive tool can be used by researchers from related fields to understand and apply the algorithms in their research. Our tool can be run in any modern browser. The tool will be permanently maintained by the second author at https://ghoshanirban.github.io/bounded-degree-plane-spanners/index.html.

A unit disk graph G on a given set of points P in the plane is a geometric graph where an edge exists between two points p, q ∈ P if and only if |pq| ≤ 1. A subgraph G0 of G is a k-hop spanner if and only if for every edge pq ∈ G, the topological shortest path between p, q in G0 has at most k edges. We obtain the following results for unit disk graphs. I Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n. II Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges. III Every n-vertex unit disk graph has a 2-hop spanner with O(n log n) edges. This is the first nontrivial construction of 2-hop spanners. IV For every sufficiently large n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. Previously, no lower bound greater than 2 was known. V For every point set on a circle, there exists a plane 4-hop spanner. As such, this provides a tight bound for points on a circle. VI The maximum degree of k-hop spanners cannot be bounded from above by a function of k.

To achieve coordination in a multi-robot system, the robots typically resort to some form of communication among each other. In most of the multi-robot coordination frameworks, high-level coordination strategies are studied but 'how' the ground-level communication takes place, is assumed to be taken care of by another program. In this paper, we study the communication routing problem for large multi-robot systems where the robots have limited communication ranges. The objective is to send a message from a robot to another in the network, routed through a low number of other robots. To this end, we propose a communication model between any pair of robots using peer-to-peer radio communication. Our proposed model is generic to any type of message and guarantees a low hop routing between any pair of robots in this network. These help the robots to exchange large messages (e.g., multi-spectral images) in a short amount of time. Results show that our proposed approach easily scales up to 1000 robots while drastically reducing the space complexity for maintaining the network information.

We revisit the online UNIT COVERING problem in higher dimensions: Given a set of n points in Rd, that arrive one by one, cover the points by balls of unit radius, so as to minimize the number of balls used. In this paper, we work in Rd using the Euclidean distance. (I) We give an online deterministic algorithm with competitive ratio O(1.321d), thereby improving on the previous record, O(2ddlog⁡d), due to Charikar et al. (2004), by an exponential factor. In particular, the competitive ratios are 5 in the plane and 12 in 3-space (the previous ratios were 7 and 21, respectively). For d=3, the ratio of our online algorithm matches the ratio of the current best offline algorithm for the same problem due to Biniaz et al. (2017), which is remarkable (and rather unusual). (II) We show that the competitive ratio of every deterministic online algorithm for UNIT COVERING in Rd under the L2 norm is at least d+1 for every d≥1. This greatly improves upon the previous best lower bound, Ω(log⁡d/log⁡log⁡log⁡d), due to Charikar et al. (2004). (III) We generalize the above result to UNIT COVERING in Rd under the LC norm, where C is a centrally symmetric convex body, via the illumination number. (IV) We obtain lower bounds of 4 and 5 for the competitive ratio of any deterministic algorithm for online UNIT COVERING in R2 and R3, respectively; the previous best lower bounds were 3 for both cases. (V) When the input points are from the square or hexagonal lattice in R2, we give deterministic online algorithms for UNIT COVERING with an optimal competitive ratio of 3. For the cubic lattice in R3, we give a deterministic online algorithm with a competitive ratio of 5.

We consider the NP-hard problem of multirobot informative path planning in the presence of communication constraints, where the objective is to collect higher amounts of information of an ambient phenomenon. We propose a novel approach that uses continuous region partitioning into Voronoi components to efficiently divide an initially unknown environment among the robots based on newly discovered obstacles enabling improved load balancing between robots. Simulation results show that our proposed approach is successful in reducing the initial imbalance of the robots’ allocated free regions while ensuring close-to-reality spatial modeling within a reasonable amount of time.

Given a set of points in the plane, the Unit Disk Cover (UDC) problem asks to compute the minimum number of unit disks required to cover the points, along with a placement of the disks. The problem is NP-Hard and several approximation algorithms have been designed over the last three decades. In this paper, we experimentally compare practical performances of some of these algorithms on massive point sets. The goal is to investigate which algorithms run fast and give good approximation in practice. We present an elementary online 7-approximation algorithm for UDC which runs in (formula presented) time on average and is easy to implement. In our experiments with both synthetic and real-world massive point sets, we have observed that this algorithm is up to 61.63 times and at least 2.9 times faster than the existing algorithms implemented in this paper. It gave 2.7-approximation in practice for the point sets used in our experiments. In our knowledge, this is the first work which experimentally compares the existing algorithms for UDC.

Information collection is an important application of multirobot systems especially in environments that are difficult to operate for humans. The objective of the robots is to maximize information collection from the environment while remaining in their path-length budgets. In this paper, we propose a novel multi-robot information collection algorithm that uses a continuous region partitioning approach to efficiently divide an unknown environment among the robots based on the discovered obstacles in the area, for better loadbalancing. Our algorithm gracefully handles situations when some of the robots cannot communicate with other robots due to limited communication ranges.

We consider the problem of information collection from a polygonal environment using a multi-robot system, subject to continuous connectivity constraints. In particular, the robots, having a common radius of communication range, must remain connected throughout the exploration maximizing the information collection. The information gained through the exploration of the terrain is wirelessly transmitted to a base station. The base station performs the centralized planning of informative paths for the robots based on the information collected by them and thereafter, the robots follow these paths. This paper formulates the problem of multi-robot informative path planning under continuous connectivity constraints as an integer program leveraging the ideas of bipartite graph matching and minimal node separators. Theoretical analysis of the proposed solution proves that the informative paths will be collision-free and will be free of both livelock and deadlock. Experimental results demonstrate the low computational requirements of our algorithm for planning the informative paths, taking only about 0.75 sec. for planning a joint set of collision-free informative locations for 10 robots.

Given a set of points P in the Euclidean plane, the classic problem of convex hull in computational geometry asks to compute the smallest convex polygon C with the vertex set X ⊆ P, such that every point in P belongs to C. In our knowledge, only two map-reduce convex hull algorithms have been designed so far. The exact map-reduce algorithm designed by Goodrich et al. (2011) is intricate and runs in constant number of rounds when the mappers and reducers have a memory of Θ(|P|ε), for a small constant ε >0. Otherwise, their algorithm runs in logarithmic number of rounds with high probability. In Big Data, easy-to-implement constant-round map-reduce algorithms are highly preferred. The other exact map-reduce algorithm, designed by Eldawy et al. (2011), does not perform efficiently when X contains sufficiently high number of points from P. In this paper, we design two new simple constant-round map-reduce algorithms along with map-reduce implementable pruning heuristics to address the above shortcomings. Our first algorithm CH-MR is exact and outperforms Eldawy et al.’s algorithm when reasonable computing resources are available, and the heuristics are able to prune away sufficient number of points. The second algorithm, named APXCH-MR, can run efficiently on any point set to return an approximate convex hull, when the input parameters are sub-linear in |P|. The designed algorithms are theoretically analyzed in the light of the popular MRC model. Our algorithms are easy to implement and do not use any complicated data structure.

We revisit the online Unit Covering problem in higher dimensions: Given a set of n points in Rd, that arrive one by one, cover the points by balls of unit radius, so as to minimize the number of balls used. In this paper, we work in R d using Euclidean distance. The current best competitive ratio of an online algorithm, O(2 d d log d), is due to Charikar et al. (2004); their algorithm is deterministic. (I) We give an online deterministic algorithm with competitive ratio O(1.321 d ), thereby improving on the earlier record by an exponential factor. In particular, the competitive ratios are 5 for the plane and 12 for 3-space (the previous ratios were 7 and 21, respectively). For d = 3, the ratio of our online algorithm matches the ratio of the current best offline algorithm for the same problem due to Biniaz et al. (2017), which is remarkable (and rather unusual). (II) We show that the competitive ratio of every deterministic online algorithm (with an adaptive deterministic adversary) for Unit Covering in Rd under the L 2 norm is at least d + 1 for every d ≥ 1. This greatly improves upon the previous best lower bound, Ω(log d/ log log log d), due to Charikar et al. (2004). (III) We obtain lower bounds of 4 and 5 for the competitive ratio of any deterministic algorithm for online Unit Covering in R 2 and respectively R 3 ; the previous best lower bounds were both 3. (IV) When the input points are taken from the square or hexagonal lattices in R 2 , we give deterministic online algorithms for Unit Covering with an optimal competitive ratio of 3.

(I) Given a segment-cuttable polygon P drawn on a planar piece of material Q, we show how to cut P out of Q by a (short) segment saw with a total length of the cuts no more than 2.5 times the optimal. We revise the algorithm of Demaine et al. (2001) so as to achieve this ratio. (II) We prove that any collection R of n disjoint1 1For brevity, a collection of disjoint polygons refers to a collection of polygons with pairwise disjoint interiors. axis-parallel rectangles drawn on a planar piece of material Q is cuttable by at most 4n rays and present an algorithm that runs in O(nlogn) time for computing a suitable cutting sequence. In particular, the same result holds for cutting with an arbitrary segment saw (of any length). (III) Given a collection P of segment-cuttable polygons drawn on a planar piece of material such that no two polygons in P touch each other, P is always cuttable by a sufficiently short segment saw. We also show that there exist collections of disjoint polygons that are uncuttable by a segment saw. (IV) Given a collection P of disjoint polygons drawn on a planar piece of material Q, we present a polynomial-time algorithm that computes a suitable cutting sequence to cut the polygons in P out of Q using ray cuts when P is ray-cuttable and otherwise reports P as uncuttable.

Let δ0(P,k) denote the degree k dilation of a point set P in the domain of plane geometric spanners. If A is the infinite square lattice, it is shown that 1 + 2 ≤ δ0(A, 3) ≤ (3 + 22)5-1/2 = 2.6065.. and δ0(A, 4) = 2. If A is the infinite hexagonal lattice, it is shown that δ0(A, 3) = 1 + 3 and δ0(A, 4) = 2. All our constructions are planar lattice tilings constrained to degree 3 or 4.

(I) We exhibit a set of 23 points in the plane that has dilation at least 1.4308, improving the previous best lower bound of 1.4161 for the worst-case dilation of plane spanners. (II) For every n ≥ 13, there exists an n-element point set S such that the degree 3 dilation of S equals 1 + 3 = 2.7321⋯ in the domain of plane geometric spanners. In the same domain, we show that for every n ≥ 6, there exists a an n-element point set S such that the degree 4 dilation of S equals 1 + (5 - 5)/2 = 2.1755⋯ The previous best lower bound of 1.4161 holds for any degree. (III) For every n ≥ 6, there exists an n-element point set S such that the stretch factor of the greedy triangulation of S is at least 2.0268.

Let δ0(P, k) denote the degree k dilation of a point set P in the domain of plane geometric spanners. If Λ is the infinite integer lattice, it is shown that [formula presented] and δ0(Λ, 4) = [formula presented]. If Λ is the infinite hexagonal lattice, it is shown that 2 ≤ δ0(Λ, 3) ≤ 3 and δ0(Λ, 4) = 2.

(I)We exhibit a set of 23 points in the plane that has dilation at least 1.4308, improving the previously best lower bound of 1.4161 for the worst-case dilation of plane spanners. (II) For every n ≥ 13, there exists an n-element point set S such that the degree 3 dilation of S denoted by δ0(S, 3) equals [formula presented] in the domain of plane geometric spanners. In the same domain, we show that for every n ≥ 6, there exists a an n-element point set S such that the degree 4 dilation of S denoted by δ0(S, 4) equals [formula presented] The previous best lower bound of 1.4161 holds for any degree. (III) For every n ≥ 6, there exists an n-element point set S such that the stretch factor of the greedy triangulation of S is at least 2.0268.

(I) Given a cuttable polygon P drawn on a piece of planar material Q, we show how to cut P out of Q by a (small) segment saw with a total length no more than 2.5 times the optimal. We revise the algorithm of Demaine et al. (2001) so as to achieve this ratio. (II) We prove that any collection R of n disjoint axis-parallel rectangles1 is cuttable by at most 4n rays and present an algorithm that runs in O(n log n) time for computing a suitable cutting sequence. In particular the same result holds for cutting with an arbitrary segment saw (of any length). (III) In contrast, we show that there exist collections of disjoint rectangles (in arbitrary orientations) that are uncuttable by a segment saw. We also present various uncuttable collections of disjoint polygons, including triangles.

Suppose that a fence needs to be protected (perpetually) by k mobile agents with maximum speeds v1,...,vk so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the idle time, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al. (2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively. In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their algorithm A2 for unidirectional patrolling of a closed fence; (ii) we present a schedule with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi.

Suppose that a fence needs to be protected by k mobile agents with maximum speeds v1, . . . , vk so that each point on the fence is visited by some agent within every duration of a predefined time. The problem is to determine if this requirement can be met, and if so, to design a suitable schedule for the agents. Alternatively, one would like to find a schedule that minimizes the idle time, that is, the longest time interval during which some point is not visited by any agent. The problem was introduced by Czyzowicz et al. (2011). We revisit this problem and discuss several strategies for the cases of open and respectively closed fence.