13517188
Computational geometry
Computational geometry [Edelsbrunner 1987; Preparata and Shamos 1985] evolves from the classical discipline of design and analysis of algorithms. It is concerned with the computational complexity of geometric problems that arise in various disciplines such as pattern recognition, computer graphics, computer vision, robotics, VLSI layout, operations research, statistics, and so on. In contrast with the classical approach to proving mathematical theorems about geometry-related problems, this discipline emphasizes the computational aspect of these problems and attempts to exploit the underlying geometric properties possible, for example, the metric space, to derive efficient algorithmic solutions. An objective of this discipline in the theoretical context is to study the intrinsic difficulty of geometric computation under a certain computation model and to devise provably efficient algorithms for the problems at hand. The measure of intrinsic difficulty of a geometric problem or efficiency of an algorithm is in terms of time and space complexities when the problem size tends to `. This is the so-called asymptotic computational complexity. Traditionally there are two types of complexity analysis of the asymptotic behavior of an algorithm: worst-case analysis and average-case analysis. In the former, the behavior of the algorithm with respect to the worst possible case of the input instance is considered, whereas in the latter, the expected behavior is considered when the input is randomly drawn from a given distribution. Recently the notion of randomized algorithms has emerged as an important area of study within algorithm design and analysis. Similar to average-case analysis, the analysis of randomized algorithms is also probabilistic with the exception that in the latter the input instance is fixed whereas the steps taken by the algorithm are random and governed by the outcomes of some probabilistic event, for example, the toss of a coin. Due to its applications to various science and engineering related disciplines, researchers in computational geometry have begun to address the efficacy of the algorithms; the issues concerning robustness and numerical stability [Fortune 1993] and the actual running times of their implementations have now become centers of attention as well. We concentrate here on the theoretical development of this field in the context of sequential computation. We adopt the real RAM (random-access machine) model of computation in which all arithmetic operations, comparisons, kth-root, exponential, or logarithmic functions take unit time. For more details refer to [Preparata and Shamos 1985]. Those who are interested in the implementations or would like more information about available software may consult the Proceedings of the Annual ACM Symposium on Computational Geometry, which has a video session, or the WWW page on Geometry in Action
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.
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.
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.
16325574
Finding an Approximate Minimum-Link Visibility Path Inside a Simple Polygon
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.
206832588
Optimization problems from feature testing of communication protocols
In feature testing of communication protocols, we want to construct a minimal number of tests with a desirable fault coverage. We model the protocols by extended finite state machines and reduce the test generation process to optimization problems on graphs. We study efficient algorithms and their complexity. We report experimental results on real systems, including Personal HandyPhone System, a 5ESS based ISDN wireless system, and 5ESS Intelligent Network Application Protocol.
32204617
A Study on Scalable Bluetooth Piconet for Secure Ubiquitous
Due to the changes in the wireless information environment, there has been an increased demand for various types of information. Accordingly, many wireless communication technologies have been studied and developed. In particular, studies on ubiquitous close distance communications are well underway. Lately, the focus has been on the Bluetooth technology due to its applicability in various environments. Applying Bluetooth connectivity to new environments such as ubiquitous or sensor networks requires finding new ways of using it. Thus, this research analyzed the vulnerability on the limited number of slaves in a piconet configuration through the current Bluetooth communication and proposed an expanded Bluetooth piconet formation method, regardless of the number of slaves inside the piconet even if it is not configured in a scatternet. In the proposed method, a security service was applied and the vulnerabilities of the current piconet configured as an expanded form of the current tree-shaped structure.
5759098
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.
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.
40350189
The Illegal Copy Protection Using Hidden Agent
There have been researches into digital Watermarking technology or Fingerprinting vigorously to safeguard Protective rights for knowledge and poverty for digital contents. DRM (Digital Rights Management) is not only Protective rights for knowledge and poverty, but also management and systems that are necessary to put out, circulate and use for contents. This technology, DRM, encrypts contents to protect digital contents and they are sold users on. Sellers transmit contents with 'Usage Right' and a license including a key of encryption. The key of encryption decodes encoded files. The right of usage restricts users' application of contents. Even if digital contents that are applied the DRM are coped illegally and circulated, contents will be protected from that because a player of DRM checks existence of licenses and allows contents to be restored. However, this method might cause users to feel inconvenient since the users can only restore contents through the licenses offered by a player or a Smartcard. If radio as well as cable is used popularly in the future, there will be a lot of limits to use those kinds of players. In the method of that, the method using players need different players in order to work successfully in wired and wireless environment. In the case of using Smartcards, there might be a dangerous situation when the Smartcards disappeared. This paper proposes two kinds of ideas. One is protecting contents from illegal acts such as illegal copies when the contents are in the process of circulation. The other is the protocol that can give users convenience. Hidden Agents are used so that contents are protected from illegal copies and illegal use in the contents and cuts off those illegal acts. The Agent will be installed without any special setup. In addition, it can replace roles of Watermarking as a protection. Therefore, this paper shows the solution of illegal copies that happens frequently.