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.     

A semi-analytic boundary element method for parabolic problems

A new semi-analytic solution method is proposed for solving linear parabolic problems using the boundary element method. This method constructs a solution as an eigenfunction expansion using separation of variables. The eigenfunctions are determined using the dual reciprocity boundary element method. This separation of variables-dual reciprocity method (SOV-DRM) allows a solution to be determined without requiring either time-stepping or domain discretisation. The accuracy and computational efficiency of the SOV-DRM is found to improve as time increases. These properties make the SOV-DRM an attractive technique for solving parabolic problems.     

Symmetric BEM formulations for 2-D steady-state and transit potential problems

This paper presents a new concept for symmetric boundary element method (SBEM) applicable to 2-D steady-state and transit potential problems. Two kinds of SBEM formulations are derived. Symmetry is obtained simply through matrix manipulation, and no hypersingularity appears. Therefore, SBEM is much easier than the traditional symmetric Galerkin BEM. Compared with the traditional asymmetric BEM, the present SBEM can reduce the computational cost for time domain problems only. However, when applied to BEM/FEM coupling procedure, SBEM can reduce the computational cost for both steady-state and time domain problems. Three numerical examples are included to illustrate the effectiveness and accuracy of the present formulations.     

Data mining of resilience indicators

In recent years, the Asia-Pacific region has experienced several financial setbacks, including speculative attacks in 1998 and the SARS outbreak in 2003. Financial stresses of this nature are unanticipated, and not all of the dangers can be predicted by the examination of market information and macroeconomic indicators. The Early Warning System (EWS) that has been adopted by the International Monetary Fund may not be able to predict future financial crises for all possible scenarios, because shocks come in many different forms. To supplement the EWS, this paper proposes a data mining framework to measure the resilience of an economy. The resilience framework does not predict a crisis, but rather assesses the current state of health of an economy and its ability to withstand a financial shock should one occur. The framework is based on a feedback system consisting of two stages. The first stage assigns a resilience score to each economy based on a fuzzy logic scoring scheme that is built on the ambiguous reasoning of experts. The second stage uses the classification tree approach to estimate thresholds for each economic indicator, and examines the quality of the fuzzy score. The result from the second stage is then passed back to the first stage as feedback. The final result is obtained when the feedback system reaches its equilibrium state. The proposed resilience framework is applied to the external-sector and the public-sector economies of several countries to illustrate its applicability.     

Exact integration in the boundary element method for two-dimensional elastostatic problems

This paper derives the exact integrations for the integrals in the boundary element analysis of two-dimensional elastostatics. For facilitation, the derivation is based on the simple forms of the fundamental functions by taking constant, discontinuous linear and discontinuous quadratic elements as examples. The efficiency and accuracy of the derived exact integrations are verified against five benchmark problems; the results indicate that the derived exact integrations significantly reduces the CPU time for forming the matrices of the boundary element analysis and solving the internal displacements.     

基于关键节点和多播节点的多播路由算法

在视频会议等多播应用中，降低多播树网络费用非常重要。本文提出了基于关键节点和目的节点的多播路由KDDMC算法。由于在算法中优先考虑采用关键节点，实现更多链路的共享，从而降低网络费用。在随机网络上的仿真结果表明，KDDMC算法的多播树网络费用优于SPH算法。同时证明了KDDMC算法的复杂度为O(n^3)，且利用所提出的路由表算法易于分布式实现。     

地下水运动数值模拟过程中边界条件问题探讨

本文对地下水运动数值模拟过程中边界条件的涵义 和处理方法进行了分析和讨论。阐述了边界条件所包含的双重意义。指出随着人类活动影响 强度的日益增大，边界条件的处理要面临一些新的更为复杂的问题。在模型预报之前必须首 先对边界条件做出预报。边界条件的预报既要考虑自然因素的作用，同时也要考虑人类活动 (人工开采和人工补给)的影响及由于邻区水流条件变化而产生的耦合效应。之后，给出了两 个应用实例。     

Boundary knot method for 2D and 3D Helmholtz and convection–diffusion problems under complicated geometry

The boundary knot method (BKM) of very recent origin is an inherently meshless, integration‐free, boundary‐type, radial basis function collocation technique for the numerical discretization of general partial differential equation systems. Unlike the method of fundamental solutions, the use of non‐singular general solution in the BKM avoids the unnecessary requirement of constructing a controversial artificial boundary outside the physical domain. The purpose of this paper is to extend the BKM to solve 2D Helmholtz and convection–diffusion problems under rather complicated irregular geometry. The method is also first applied to 3D problems. Numerical experiments validate that the BKM can produce highly accurate solutions using a relatively small number of knots. For inhomogeneous cases, some inner knots are found necessary to guarantee accuracy and stability. The stability and convergence of the BKM are numerically illustrated and the completeness issue is also discussed. Copyright © 2003 John Wiley & Sons, Ltd.     

一个表示和运用非功能性需求的框架

本文分析了一个软件开发进程中表示和运用非功能性需求的综合框架，该框架的目的是开发一套技术以调整软件开发进程中的设计决策，从而强调了依据非功能需求，探索合理化的软件开发进程。     

Fundamental solutions for half plane with an oblique edge crack

An elastic half plane with an oblique edge crack is considered in this paper. A pair of concentrated forces or point dislocations is assumed to act at an arbitrary point in the half plane. The half plane with an edge crack is first mapped into a unit circle by a rational mapping function so that the following analysis can be carried out on the mapped plane analytically. Then the complex stress functions are derived by separating the whole problem into two parts; one is the principal part corresponding to the infinite plane acted on by concentrated forces or dislocations, the other is the holomorphic part, which can be determined by making use of the property of regularity of complex stress functions. The stress intensity factors of the crack can be calculated with different inclined angles of the crack, and the displacement and stress components at an arbitrary position in the half plane can be expressed explicitly.