A generalized approach to the reconstruction of a restricted class of digitized planar curves

Reconstruction of an original continuous curve and the estimation of its parameters from the digitized version of the curve is a challenging problem, as quantization always causes some loss of information. In this paper, we have developed a scheme for reconstruction which is applicable to a class of curves having at the most two parameters. The class of curves for which the scheme works has also been characterized. We have shown that for one-parameter curves the exact domain of values of the parameter can be obtained. But in the two-parameter case, only the smallest rectangle containing the domain can be realised. The distinctive feature of our scheme is that it provides a unified approach to solve the reconstruction and the domain-finding problem for a class of curves.     

Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

Simple algorithms for searching a polygon with flashlights

The k-searcher is a mobile guard whose visibility is limited to k rays emanating from her position, where the direction of each ray can be changed continuously with bounded angular rotation speed. Given a polygonal region P, is it possible for the k-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within P? We present O(n²)-time algorithms for constructing a search schedule of the 1-searcher and the 2-searcher, respectively. Our framework for the 1-searcher can be viewed as a modification of that of LaValle et al. [Proc. 16th ACM Symp. on Computational Geometry, 2000, pp. 260-269] and is naturally extended for the 2-searcher.     

Reliability models for computer systems: An overview including dataflow graphs

The reliability of a system is the probability that the system will perform its intended mission under given conditions. This paper provides an overview of the approaches to reliability modelling and identifies their strengths and weaknesses. The models discussed include structure models, simple stochastic models and decomposable stochastic models. Ignoring time-dependence, structure models give reliability as a function of the topological structure of the system. Simple stochastic models make direct use of the properties of underlying stochastic processes, while decomposable models consider more complex systems and analyse them through subsystems. Petri nets and dataflow graphs facilitate the analysis of complex systems by providing a convenient framework for reliability analysis.     

局域网服务器缓冲区容量的Petri网设计方法

本文在分析局域网服务器信息缓冲区、数据包接受和发送缓冲区的相互关系基础上提出一种新的局域网服务器缓冲区设计方法─—广义随机Ｐｅｔｒｉ网方法，并给出了局域网服务器信息缓冲区的广义随机Ｐｅｔｒｉ网模型。该设计方法理论完备、严谨实用，且不再局限于追求某一边界值（上限或下限），并且避免了排队理论处理多级服务的繁琐公式。最后本文用一例题说明了这种方法的应用。     

直接基于灰度图象的多尺度角点检测方法

在计算机视觉领域中角点特征的提取具有相当重要的地位，因为角点包含了丰富的信息。本文提出了一种新的利用微分几何和小波变换的多尺度角点检测方法，它具有以下特点：一是无须提取边缘图象，而是直接在灰度图象上提取角点。二是由于利用了小波变换技术从多个尺度上进行角点的提取，所以它既较为有效的抑制了由于噪音等原因造成的诸多错误角点位置的出现，又能得到较为精确的有用角点位置。最后通过实验证明了本算法有效性。     

三维结构可靠度对随机变量的敏感性研究

本文基于三维随机有限元提出了结构点可靠度、失效模式的可靠度及整个结构体系的可靠度分别对随机变量的＂分布参数＂和＂极限状态方程参数＂的敏感性计算方法，并以一典型重力坝为例进行了计算，得出了若干有益的结论。     

A Dynamic Dictionary for Priced Information with Application

In this paper we design a dynamic dictionary for the priced information model initiated by Charikar et al. Assume that a set S consisting of n elements is given such that each element has an associated price, a positive real number. The cost of performing an operation on elements of S is a function of their prices. The cost of an algorithm is the sum of the costs of all operations it performs. The objective is to design algorithms which incur low cost. In this model we propose a dynamic dictionary, supporting search, insert and delete, for keys drawn from a linearly ordered set. As an application we show that the dictionary can be used in computing the trapezoidal map of a set of line segments, a fundamental problem in computational geometry.     

A visual tool for computer supported learning: The robot motion planning example

We introduce an effective computer aided learning visual tool (CALVT) to teach graph-based applications. We present the robot motion planning problem as an example of such applications. The proposed tool can be used to simulate and/or further to implement practical systems in different areas of computer science such as graphics, computational geometry, robotics and networking. In the robot motion planning example, CALVT enables users to setup the working environment by creating obstacles and a robot of different shapes, specifying starting and goal positions, and setting other path or environment parameters from a user-friendly interface. The path planning system involves several phases. Each of these modules is complex and therefore we provide the possibility of visualizing graphically the output of each phase. Based on our experience, this tool has been an effective one in classroom teaching. It not only cuts down, significantly, on the instructor’s time and effort but also motivates senior/graduate students to pursue work in this specific area of research.     

Optimal predictor for a singular random process

An optimal predictor is developed for a singular random process generated by a known system driven by a white noise sequence. The properties of the predictor are compared with those of the optimal predictor for a nonsingular random process.