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.
14910989
Geosheet: A Distributed Visualization Tool for Geometric Algorithms
GeoSheet (version 1.0) is an interactive visualization tool for visualizing geometric algorithms in distributed environments. It provides features such as interactive visualization of program states for debugging, high-level graphical input/output manipulation facilities for geometric objects, reuse of existing data structures and algorithms implementation, and more importantly distributed executions on heterogeneous machines at different sites. To minimize development effort of the tool we make use of existing software packages available in public domain. Specifically we extend Xfig with a message-driven interface and a socket-based interprocess communication (IPC) mechanism. This extended-Xfig is the backbone of this version of the tool. Object-oriented programming methodology is used to construct the visualization interface. By deriving from traditional data type and algorithm libraries, our abstract GeoObject representation super-classes are easy to use, easy to construct, and highly portable. Although GeoSheet is not restricted to a particular application domain or any programming language, this release only contains geometric algorithm implementations in C++ and LEDA. We hope that the geometric algorithm designers will find it useful when they develop their algorithms.
15124242
Solving the all-pair shortest path query problem on interval and circular-arc graphs
In this paper, we study the following all-pair shortest path query problem: Given the interval model of an unweighted interval graph of n vertices, build a data structure such that each query on the shortest path (or its length) between any pair of vertices of the graph can be processed eeciently (both sequentially and in parallel). We show that, after sorting the input intervals by their endpoints, a data structure can be constructed sequentially in O(n) time and O(n) space; using this data structure, each query on the length of the shortest path between any two intervals can be answered in O(1) time, and each query on the actual shortest path can be answered in O(k) time, where k is the number of intervals on that path. Furthermore, this data structure can be constructed optimally in parallel, in O(log n) time using O(n= log n) CREW PRAM processors; each query on the actual shortest path can be answered in O(1) time using k processors. Our techniques can be extended to solving the all-pair shortest path query problem on circular-arc graphs, both sequentially and in parallel, in the same complexity bounds. As an immediate consequence of our results, we improve by a factor of n the space complexity of the previously best known sequential all-pair shortest path algorithm for unweighted interval graphs.
38005392
Towards Web-Based Computing
In a problem solving environment for geometric computing, a graphical user interface, or GUI, for visualization has become an essential component for geometric software development. In this paper we describe a visualization system, called GeoJAVA, which consists of a GUI and a geometric visualization library that enables the user or algorithm designer to (1) execute and visualize an existing algorithm in the library or (2) develop new code over the Internet. The library consists of geometric code written in C/C++. The GUI is written using the Java programming language. Taking advantage of the socket classes and system-independent application programming interfaces (API's) provided with the Java language, GeoJAVA offers a platform independent environment for distributed geometric computing that combines Java and C/C++. Users may remotely join a "channel" or discussion group in a location transparent manner to do collaborative research. The visualization of an algorithm, a C/C++ program located locally or remotely and controlled by a "floor manager", can be viewed by all the members in the channel through a visualization sheet called GeoJAVASheet. A chat box is also provided to enable dialogue among the members. Furthermore, this system not only allows visualization of pre-compiled geometric code, but also serves as a web-based programming environment where the user may submit a geometric code, compile it with the libraries provided by the system, and visualize it directly over the web sharing it with other users immediately.
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.
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.
45853491
Testing Finite-State Machines: State Identification and Verification
We study the complexity of two fundamental problems in the testing of finite-state machines. 1) Distinguishing sequences (state identification). We show that it is PSPACE-complete to determine whether a finite-state machine has a preset distinguishing sequence. There are machines that have distinguishing sequences, but only of exponential length. We give a polynomial time algorithm that determines whether a finite-state machine has an adaptive distinguishing sequence. (The previous classical algorithms take exponential time.) Furthermore, if there is an adaptive distinguishing sequence, then we give an efficient algorithm that constructs such a sequence of length at most n(n/spl minus/1)/2 (which is the best possible), where n is the number of states. 2) Unique input output sequences (state verification). It is PSPACE-complete to determine whether a state of a machine has a unique input output sequence. There are machines whose states have unique input output sequences but only of exponential length. >
3246222
An Efficient Algorithm for Minimizing Real-time Transition Systems
We address the problem of performing simultaneously reachability analysis and minimization of real-time transition systems represented by timed automata , i.e., automata extended with a finite set of clock variables. The transitions of the automaton may depend on the values of the clocks and may reset some of the clocks. An efficient algorithm is presented for minimizing a system with respect to a given initial partition that respects the enabling conditions of the transitions of the timed automaton. Our algorithm generates the portion of the minimized system that is reachable from a given initial configuration in time polynomial in the input and the size of the minimal reachable system.
16966197
Integrated system interoperability testing with applications to VoIP
This work has been motivated by the need to test interoperability of systems carrying voice calls over the IP network. The voice over IP (VoIP) systems must be integrated and interoperate with the existing public switched telephone network (PSTN) before they are widely adopted. Standards have been developed to address this problem, but unfortunately different standards bodies and commercial consortiums have defined different standards. Furthermore, the prevailing VoIP standard such as H.323 is incomplete, complex, and presents the implementers with "vendors latitudes". As a result, there is no guarantee that the integrated VoIP systems would interoperate properly even if the implementations are all H.323-compliant. Thus interoperability testing has become indispensable. We want to test all the system interoperations by exercising all the required patterns of "interoperating behaviors". On the other hand, test execution in real environment is expensive, and we want to minimize the number of tests while maintaining the coverage. We present a general method for automatic generation of test cases, which cover all the required system interoperations and contain a minimal number of tests. We study data structures and efficient test generation algorithms, which take time proportional to the total test case size. Finally, we report experimental results on VoIP systems.
53246202
Energy-optimized image communication on resource-constrained sensor platforms
12480757
Robotic sensing for the partially sighted
Partial sightedness is a sensory disability which can to some extent be alleviated by artificial aids. Many of the sensory methods used in robotics can be applied in attempts to recapture some of the sensory information a partially sighted person has lost. This paper describes a device which uses sonar and stereo vision sensors for this task. The device is portable, and is worn by the user, giving them freedom of movement over kerbs, stairs and rough ground. Sensor motion during walking is measured using visual egomotion recovery and odometry, and has been modelled to allow compensation in the sensor readings. A ground position estimate is continually updated by scene ground-plane fitting, or from the walk-motion model, and is used to classify scene features as obstacles or parts of the ground. Methods for the robust reconstruction of image points and lines into scene features are developed. The recognition of world objects of exceptional significance to a mobile person - kerbs and stairs - is given particular attention. A user interface, which has undergone limited real world testing, is also described. Experimental results are presented for the various parts of the system.