13394130
Two-Guard Walkability of Simple Polygons
A pair of points s and g on the boundary of a simple polygon P admits a walk if two guards can simultaneously walk along the two boundary chains of P from s to g such that they are always visible to each other. The walk is a counter-walk if one guard moves from s to g while the other moves from g to s in the same direction along the boundary and they are always visible to each other. The (counter-)walk is straight if no backtracking is necessary during the (counter-)walk. In this paper, we show that, given a polygon with n vertices, to test if there exists (s,g) that admits a (straight) (counter-)walk can be solved in time O(n log n) and in linear space. Also we compute all (s,g)'s that admit a (straight) walk in O(n log n) time and all vertex pairs that admit a (straight) counter-walk in O(n log n + m), where m is O(n2).
6583254
Rectilinear Path Problems among Rectilinear Obstacles Revisited
Efficient algorithms are presented for finding rectilinear collision-free paths between two given points among a set of rectilinear obstacles. The results improve the time complexity of previous results for finding the shortest rectilinear path, the minimum-bend shortest rectilinear path, the shortest minimum-bend rectilinear path and the minimum-cost rectilinear path. For finding the shortest rectilinear path, a graph-theoretic approach is used and an algorithm is obtained with $O(m\log t+ t\log^{3/2} t)$ running time, where $t$ is the number of extreme edges of given obstacles and $m$ is the number of obstacle edges. Based on this result an $O(N\log N+(m+N)\log t + (t+N)\log^2 (t+N))$ running time algorithm for computing the $L_1$ minimum spanning tree of given $N$ terminals among rectilinear obstacles is obtained. For finding the minimum-bend shortest path, the shortest minimum-bend rectilinear path, and the minimum-cost rectilinear path, we devise a new dynamic-searching approach and derive algorithms that run in $O(m\log^2m)$ time using $O(m\log m)$ space or run in $O(m\log^{3/2}m)$ time and space.
18326125
Finding Rectilinear Paths Among Obstacles in a Two-Layer Interconnection Model
Finding the best rectilinear path with respect to the bends and teh lengths of paths connecting two given points in the presence of rectilinear obstacles in a two-layer model is studied in this paper. In this model, rectilinear obstacles on each layer are specified separately, and the orientation of routing in each layer is fixed. An algorithm is presented to transform any problem instance in the two-layer model to one in a one-layer model, so that almost all algorithms for finding rectilinear paths among obstacles in the plane can be applied. The transformation algorithm runs in O(e log e) time where e is the number of edges on obstacles lying on both layers. A direct graph-theoretic approach to finding a shortest path in the two-layer model, which is easier to implement is also presented. The algorithm runs in O(e log2 e) time.
16325574
Finding an Approximate Minimum-Link Visibility Path Inside a Simple Polygon
10484740
Labeling Points on a Single Line
In this paper, we consider a map labeling problem where the points to be labeled are restricted on a line. It is known that the 1d-4P and the 1d-4S unit-square label placement problem and the Slope-4P unit-square label placement problem can both be solved in linear time and the Slope-4S unit-square label placement problem can be solved in quadratic time in Ref. [8]. We extend the result to the following label placement problem: Slope-4P fixed-height (width) label or elastic label placement problem and present a linear time algorithm for it provided that the input points are given sorted. We further show that if the points are not sorted, the label placement problems have a lower bound of Ω(n log n), where n is the input size, under the algebraic computation tree model. Optimization versions of these point labeling problems are also considered.
37965905
Rectilinear Paths among Rectilinear Obstacles
Given a set of obstacles and two distinguished points in the plane the problem of finding a collision-free path subject to a certain optimization function is a fundamental problem that arises in many fields, such as motion planning in robotics, wire routing in VLSI and logistics in operations research. In this survey we emphasize its applications to VLSI design and limit ourselves to the rectilinear domain in which the goal path to be computed and the underlying obstacles are all rectilinearly oriented, i.e., the segments are either horizontal or vertical. We consider different routing environments, and various optimization criteria pertaining to VLSI design, and provide a survey of results that have been developed in the past, present current results and give open problems for future research.
36612071
SPY-TEC: An efficient indexing method for similarity search in high-dimensional data spaces
Most of all index structures based on the R-tree have failed to support eAcient indexing mechanisms for similarity search in high-dimensional data spaces. This is due to the fact that most of the index structures commonly use balanced split strategy in order to guarantee storage utilization and the shape of queries for similarity search is a hypersphere in high-dimensional spaces. In this paper, we propose the Spherical Pyramid-Technique (SPY-TEC), an eAcient indexing method for similarity search in high-dimensional data space. The SPY-TEC is based on a special partitioning strategy, which is to divide the d-dimensional data space first into 2d spherical pyramids, and then cut the single spherical pyramid into several spherical slices. This partition provides a transformation of d-dimensional space into one-dimensional space as the Pyramid-Technique [14] does. Thus, we are able to use a B a -tree to manage the transformed one-dimensional data. We also propose the algorithms to process hyperspherical range queries on the data space partitioned by this partitioning strategy. Finally, we show that the SPY-TEC clearly outperforms other related techniques including the Pyramid-Technique in processing hyperspherical range queries through various experiments using synthetic and real data. ” 2000 Elsevier Science B.V. All rights reserved.
552424
A polynomial algorithm for gateway generation from formal specifications
A systematic procedure that takes exponential time to synthesize protocol converters from formal specifications is presented. The algorithm proceeds in two steps: compute the largest common subset of services provided by the two mismatched protocols, and reduce the converter, retaining common services, without traversing the entire machine that represents the composition of the two mismatched protocols. In a number of cases, the converter can be constructed by a memoryless translation of messages from one protocol to another. Conditions under which such stateless conversion is possible are given. Two examples are presented to illustrate the techniques. In the first example, a converter that interconnects a half-duplex protocol with a full-duplex protocol from their formal specifications is computed. In the second example, the polynomial procedure is applied to computation of a converter for interconnecting the SNR and TCP protocols. >
23137458
Testing Finite State Machines: Fault Detection
Abstract We present simple randomized algorithms for the fault detection problem : Given a specification in the form of a deterministic finite state machine A and an implementation machine B , determine whether B is equal to A . If A has n states and p inputs, then in randomized polynomial time we can construct with high probability a checking sequence of length O ( pn 4 log n ), i.e., a sequence that detects all faulty machines with at most n states. Better bounds can be obtained in certain cases. The techniques generalize to partially specified finite state machines.
33611736
RAGOBOT: A New Platform for Wireless Mobile Sensor Networks
We present Ragobot, a fully-featured validated platform for use in mobile sensor networks. Ragobot is a robot of small dimensions with features that surpass those provided by many other robots in this category. Ragobot hardware and software are implemented with modularity as one of the main considerations; therefore, these are easy to upgrade and customize according to the needs of each specific application. Moreover, we present Ragoworld, a controlled physical space for the development and evaluation of mobile sensor network algorithms.
46374921
A Formal Specification of the ATM ABR Rate Control Scheme
Abstract Formal specifications are indispensable for computer-aided validation, verification, and testing of communication protocols. However, a large number of practical protocols, including those for ATM, have only informal English specifications. A formal specification helps in achieving a consistent interpretation and thus increases the likelihood of interoperable implementations. As a case study, we consider an important protocol — ATM's Available Bit Rate (ABR) service specification. The ABR source/destination policies have been specified using an English description in the main body of the ATM Forum's draft Traffic Management specification, from which it is hard to conduct a formal analysis. It must be noted however that considerable energy has been spent in providing a reasonably precise specification, while allowing for appropriate implementation latitude. However, an English description still has the potential for different interpretations, which may lead to discrepancy in different vendors' implementations and cause serious problems in interoperability of the communication entities made by different manufacturers. We model the ABR protocols by parameterized communicating extended finite state machines with timers, which is often called a transition system. The protocol is formally specified by the specification of the transitions of the system. We also provide insights gained in the derivation of the formal specification. Furthermore, we introduce a scheduler, involved in transmitting queued cells at the allowed cell rate to meet the minimal requirements from the source/destination protocols. We present the transitions for the source/destination/scheduler machines primarily for transmitting in-rate cells.