2528129
Rectilinear Paths Among Rectilinear Obstacles
We address problems of finding rectilinear paths among rectilinear obstacles subject to certain optimization criteria. They have applications in the fields of motion planning and computer-aided circuit design. The criteria that we consider include minimizing the length of the path, minimizing the number of bends on the path, bounding one of the two factors (length and number of bends) and minimizing the other, and minimizing a given non-decreasing function of both the length and the number of bends. The length measure of a rectilinear path can be the total length of all the segments of the paths or just the sum of lengths of all the vertical or horizontal segments of the path. Besides the various optimization criteria for the paths that we look for, the routing environments may have different constraints. For example, the obstacles can be rectangular or rectilinear, the orientations of the path may be restricted to be horizontal or vertical on different layers in a two-layer interconnection model, or the path can penetrate the obstacles and pay extra costs. Previous results and problem solving approaches are summarized and compared to ours in this dissertation. 
We obtain more efficient algorithms for finding a shortest rectilinear path between two points, minimum spanning tree of a set of points, and for finding assorted paths taking both length and the number of bends into consideration. We also derive a general problem transformation scheme to convert an instance in two-layer model into an equivalent problem in one-layer model, for which previously obtained algorithms under different objective functions are applicable.
34901507
A faster algorithm for rubber-band equivalent transformation for planar VLSI layouts
In this paper we consider the problem of transforming a single-layer topological routing of n two-terminal nets into a rubber-band equivalent using rectilinear wires in the presence of rectilinear circuit modules. Given a topological planar VLSI layout sketch with |F| features and |W| noncrossing wire segments connecting n two-terminal nets, we present an O(|F|/spl middot/|W|) time algorithm to do the vertex-disjoint rubber-band equivalent transformation of these n nets if it exists. The algorithm consists of two phases, computing a loose homotopy with four spokes matrices, and computing a vertex-disjoint rubber-band equivalent of the given homotopy, each phase taking O(|F|/spl middot/|W|) time and space. Both complexities are asymptotically optimal in the worst case. From the vertex-disjoint rubber-band equivalent of the given homotopy, one can obtain the detailed routing within the same time complexity. Experimental results are also presented.
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.
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.
16325574
Finding an Approximate Minimum-Link Visibility Path Inside a Simple Polygon
3145025
Quantitative Evaluation of the Exploration Strategies of a Mobile Robot
This article describes an experimental investigation into the map-building and exploration capabilities of a mobile robot. Two types of map are used: a set of line and point features, and a grid-based free-space map. Potential features are ex tracted from sonar range readings and classed as "confirmed" if detected repeatedly. The free-space map is derived from the set of confirmed features. A distance-transform algorithm is then used to plan paths on this map. The confirmed features are used by a Kalman filter to estimate the robot's position relative to known objects. This research places exceptional stress on the need for practical experimentation and quantitative, statistical evaluation of the results. For this to be possible, it is essential to have a clearly defined measure of map quality. A novel metric is defined that predicts the effectiveness of the robot if it were to use the map to execute a set of test tasks. Exploration strategies are tested experimentally in a range of environments and starting positions. The results are eval uated and compared statistically. The tested strategies range from those that are totally reactive, such as wall-following, to those that use the developing map to focus attention on the un examined parts of the environment. The most promising results are observed from hybrid exploration strategies that combine the robustness of reactive navigation and the directive power of map-based strategies.
19220261
Path protection and blocking probability minimization in optical networks
We study the problem of shared path protection in optical networks from the viewpoint of blocking probability minimization. Unlike the worst-case approach common in other studies, which typically deals with one failure at a time and requires recomputation of the protection paths after every failure, our framework assumes a fixed path protection strategy for every connection that does not change in response to failures in other connections, which is more realistic for networks with high failure rates. We study backup-path strategy configurations that minimize the blocking probability and derive various properties. We show that configurations which do not have partial overlaps among connections backup paths are optimal in a rather general sense. We discuss the minmax optimal configuration properties and present an efficient algorithm for finding it in a case of special interest, while showing it to be NP-hard in general. In addition, we discuss the properties of the game resulting if each connection chooses its backup path selfishly; we show it to belong to the class of potential games, well-studied in the game theory literature, and derive several further properties resulting from its specific structure.
7389460
Fault Detection of Hierarchical Networks with Probabilistic Testing Algorithms
As communications networks are expanding to larger areas the control and maintenance of routing information are becoming a formidable task. To cope with its size and complexity and to make the network reliable and scalable hierarchical network has been proposed with new features to support the information infrastructure. However, the network hierarchy adds more complications to the network design and implementations and that hampers the network reliability and quality of services. Conformance testing is known to be a powerful tool for network fault detection yet most of the works in the published literature are on networks without hierarchy. We present probabilistic algorithms for testing hierarchical networks along with the added features. Based on a formal model of the networks, we provide a formal analysis that shows that our probabilistic algorithms guarantee a high fault coverage with a feasible number of tests. To further reduce the number of tests we identify test equivalence classes and that enables us to significantly reduce the number of tests yet without losing the fault coverage. Experimental results on Internet OSPF protocol are reported.
206055518
Approximate evaluations of characteristic polynomials of Boolean functions
Motivated by combinational circuit verification and testing, we study the approximate evaluation of characteristic polynomials of Boolean functions. We consider an oracle model in which the values of the characteristic polynomials are approximated using the evaluations of the corresponding Boolean functions. The approximation error is defined in the worst case, average case and randomized settings. We derive lower bounds on the approximation errors in terms of the number of Boolean function evaluations. We design algorithms with an error that matches the lower bound. Let k(e,n) denote the minimal number of Boolean function evaluations needed to reduce the initial error by a factor of e where n is the number of Boolean variables. We show that k(e,n) is exponential in n in the worst and average case settings, and that it is independent of n and of order e−2 in the randomized setting.
6192203
Authentication for Single/Multi Domain in Ubiquitous Computing Using Attribute Certification
The Ubiquitous computer environment is thing which invisible computer that is not shown linked mutually through network so that user may use computer always is been pervasive. Intend computing environment that can use easily as user wants and it is the smart environment that user provides context awareness that is wanting computing environment. This Ubiquitous computing contains much specially weak side in security. Masquerade attack of that crawl that is quoted to user or server among device that is around user by that discrete various computing devices exist everywhere among them become possible. Hereupon, in this paper, proposed method that has following characteristic. Present authentication model through transfer or device. Suggest two method that realize authentication through device in case of moved to method (MD: Multi Domain) and user ownself space (SD: Single Domain) that realize authentication through device in case of moved user's direct path who device differs.