This paper addresses a synchronization problem that arises when a team of robots needs to communicate while repeatedly performing assigned tasks in a cooperative scenario. Each robot has a limited communication range and moves along a previously defined closed trajectory. When two robots are close enough, a communication link may be established, allowing the robots to exchange information. The goal is to schedule the motions such that the entire system can be synchronized for maximum information exchange; that is, every pair of neighbors always visit the feasible communication link at the same time. An algorithm for scheduling the team of robots in this scenario is proposed and a robust framework that assures the synchronization of a large team of robots is presented. Simulations, experiments, and computational results demonstrate the applicability of the algorithm. The approach allows the design of fault-tolerant systems that can be used for multiple tasks, such as surveillance, area exploration, and searching for targets in hazardous environments, among others.

This paper addresses a synchronization problem that arises when a team of aerial robots (ARs) need to communicate while performing assigned tasks in a cooperative scenario. Each robot has a limited communication range and flies within a previously assigned closed path. When two robots are close enough, a communication link may be established allowing the robots to share information. The goal is to schedule the flights such that the entire system can be synchronized for maximum information exchange, that is, every pair of neighbors are on the feasible communication link at the same time. We propose an algorithm for scheduling a team of robots in this scenario and propose a robust framework where the synchronization of a large team of robots is assured. The approach allows us to design a fault-tolerant system that can be used for multiple tasks such as surveillance, area exploration, searching for targets in a hazardous environment, and assembly and structure construction, to name a few.

This paper discusses the computation of optimal coverage paths in an ad-hoc network consisting of n sensors. Improved algorithms, with a preprocessing time of O(n log n), to compute a maximum breach/support path P in optimal (|P|) time or the maximum breach/support value in O(1) time are presented. Algorithms for computing a shortest path that has maximum breach/support are also provided. Experimental results for breach paths show that the shortest path length is on the average 30% less and is not much worse that the ideal straight line path. For applications that require redundancy (i.e., detection by multiple sensors), a generalization of Voronoi diagrams allows us to compute maximum breach paths where breach is defined as the distance to the kth nearest sensor in the field. Extensive experimental results are provided.

We present a new approach for approximate nearest neighbor queries for sets of high dimensional points under any L/sub t/-metric, t=1,...,/spl infin/. The proposed algorithm is efficient and simple to implement. The algorithm uses multiple shifted copies of the data points and stores them in up to (d+1) B-trees where d is the dimensionality of the data, sorted according to their position along a space filling curve. This is done in a way that allows us to guarantee that a neighbor within an O(d/sup 1+1/t/) factor of the exact nearest, can be returned with at most (d+1)log, n page accesses, where p is the branching factor of the B-trees. In practice, for real data sets, our approximate technique finds the exact nearest neighbor between 87% and 99% of the time and a point no farther than the third nearest neighbor between 98% and 100% of the time. Our solution is dynamic, allowing insertion or deletion of points in O(d log/sub p/ n) page accesses and generalizes easily to find approximate k-nearest neighbors.

A productivity-driven methodology for incremental floorplanning is described and the constrained polygon transformation problem , a key step of this methodology, is formulated. The input to the problem consists of a floorplan computed using area estimates and the actual area required for each subcircuit of the floorplan. Informally, the objective is to change the areas of the modules without drastically changing their shapes or locations. We show that the constrained polygon transformation problem is NP-hard and present several fast algorithms that produce results within a few percent of a theoretical lower bound on several floorplans.

The coming years will witness dramatic advances in wireless communications as well as positioning technologies. As a result, tracking the changing positions of objects capable of continuous movement is becoming increasingly feasible and necessary. The present paper proposes a novel, R*-tree based indexing technique that supports the efficient querying of the current and projected future positions of such moving objects. The technique is capable of indexing objects moving in one-, two-, and three-dimensional space. Update algorithms enable the index to accommodate a dynamic data set, where objects may appear and disappear, and where changes occur in the anticipated positions of existing objects. A comprehensive performance study is reported.

Past R-tree studies have focused on the number of nodes visited as a metric of query performance. Since database systems usually include a buffering mechanism, we propose that the number of disk accesses is a more realistic measure of performance. We develop a buffer model to analyze the number of disk accesses required for spatial queries using R-trees. The model can be used to evaluate the quality of R-tree update operations, such as various node splitting and tree restructuring policies, as measured by query performance on the resulting tree. We use our model to study the performance of three well-known R-tree loading algorithms. We show that ignoring buffer behavior and using number of nodes accessed as a performance metric can lead to incorrect conclusions, not only quantitatively, but also qualitatively. In addition, we consider the problem of how many levels of the R-tree should be pinned in the buffer.

Past R tree studies have focused on the number of nodes visited as a metric of query performance. Since database systems usually include a buffering mechanism, we propose that the number of disk accesses is a more realistic measure of performance. We develop a buffer model to analyze the number of disk accesses required for spatial queries using R trees. The model can be used to evaluate the quality of R tree update operations, such as various node splitting and tree restructuring policies, as measured by query performance on the resulting tree. We use our model to study the performance of three well known R tree packing algorithms. We show that ignoring buffer behavior and using number of nodes accessed as a performance metric can lead to incorrect conclusions, not only quantitatively, but also qualitatively. In addition, we consider the problem of how many levels of the R tree should be pinned in the buffer.

Presents the results from an extensive comparison study of three R-tree packing algorithms: the Hilbert and nearest-X packing algorithms, and an algorithm which is very simple to implement, called the STR (Sort-Tile-Recursive) algorithm. The algorithms are evaluated using both synthetic and actual data from various application domains including VLSI design, GIS (Tiger files), and computational fluid dynamics. Our studies also consider the impact that various degrees of buffering have on query performance. Experimental results indicate that none of the algorithms as best for all types of data. In general, our new algorithm requires up to 50% fewer disk accesses than the best previously proposed algorithm for point and region queries on uniformly distributed or mildly skewed point and region data, and approximately the same for highly skewed point and region data.

We present two practical algorithms for partitioning circuit components represented by rectilinear polygons so that they can be stored using the L-shaped corner stitching data structure; i.e., our algorithms decompose a simple polygon into non-overlapping L-shapes and rectangles by using horizontal cuts only. The more general of our algorithms computes an optimal configuration for a wide variety of optimization functions, while the other computes a minimum configuration of rectangles and L-shapes. Both run in O(n+h log h) time, where n is the number of vertices in the polygon and h is the number of H-pairs. Experimental results on VLSI data demonstrate the gains in performance for corner stitching obtained by using our algorithms instead of traditional rectangular partitioning algorithms.

No abstract available.

Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, c, of different orientations of the line segments or polygons in a practical VLSI mask design is small relative to the number, n, of segments or polygon edges. Instead they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop and implement a practical algorithm for net extraction that runs in O(cn log n) time and O(n) space, which is optimal for fixed c. The algorithm uses only integer operations and is, as a result, numerically stable. Experiments indicate that the algorithm will outperform existing algorithms on practical VLSI designs. We expect that the techniques presented will be useful in other VLSI/CAD problems that operate with restricted orientation geometries.

We present two practical algorithms for partitioning circuit components represented by rectilinear polygons so that they can be stored using the L-shaped corner stitching data structure; that is, our algorithms decompose a simple polygon into a set of nonoverlapping L-shapes and rectangles by using horizontal cuts only. The more general of our algorithms computes and optimal configuration for a wide variety of optimization functions, whereas the other computes a minimum configuration of rectangles and L-shapes. Both algorithms run in O ( n + h log h time, where n is the number of vertices in the polygon and h is the number of H-pairs. Because for VLSI data h is small, in practice these algorithms are linear in n . Experimental results on actual VLSI data compare our algorithms and demonstrate the gains in performance for corner stitching (as measured by different objective functions) obtained by using them instead of more traditional rectangular partitioning algorithms.

It is shown that given a set of n line segments, their connected components can be computed in time O(n/sup 4/3/log/sup 3/n). A bound of o(n/sup 4/3/) for this problem would imply a similar bound for detecting, for a given set of n points and n lines, whether some point lies on some of the lines. This problem, known as Hopcroft's problem, is believed to have a lower bound of /spl Omega/(n/sup 4/3/). For the special case when for each segment both endpoints fall inside the same face of the arrangement induced by the set of segments, we give an algorithm that runs in O(nlog/sup 3/n) time.>

A TCN is a hierarchical interconnection network where isomorphic clusters are connected using a complete graph at the highest level of hierarchy. We extend the concept of TCN to the dynamic domain and reduce the hardware complexity in the static domain. The resulting networks outperform both its non-hierarchical and hierarchical counterparts, while improving on the congestion and fault-tolerance characteristics of the latter; they also have optimal connectivity, high bisection width, low degree, cost and diameter, and low average distance under both uniform and non-uniform traffic. For instance, with dynamic clusters we obtain the same delay as the corresponding non hierarchical multistage network at 1/2 the cost; while the maximum and average delays are typically 2/3 and 3/4 of those in a comparable HMIN, at approximately the same cost. In the static case, using hypercube clusters, the degree, diameter and cost are approximately 1/2, 3/4 and 3/8 of the same parameters in a comparable size hypercube; while the diameter and average distance are typically 1/2 and 3/4 of those in traditional HINs. In case of mesh clusters, the diameter and cost are reduced even further, by an amount proportional to their square root.

Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, c, of different orientations of the line segments or polygon edges in a practical VLSI mask design is small relative to the number, n, of segments or edges. Instead, they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop a simple and practical algorithm for net extraction that runs in O(cn log n) time and O(n) space, which is optimal for fixed c. Experiments indicate that the algorithm will generally outperform existing algorithms on practical VLSI designs. We expect that the techniques presented will be useful in other VLSI CAD problems that operate with restricted orientation geometries.

A method for constructing hierarchical in terconnection networks is presented. The method is based on connecting isomorphic clusters using a complete graph as the higher level network. Applying it to various classes of graphs, including hypercubes and meshes, results in networks with optimal connectivity, high bisection width, low degree, diameter and cost. With hypercube clusters, the degree, diameter and cost are approximately | , | and j of the same parameters in a comparable size hy percube. With mesh clusters, the performance parame ters are polynomially better than those in a similar size mesh.