The 1-center problem in the plane with independent random weights

The 1-center problem in the plane with random weights has only been studied for a few specific probability distributions and distance measures. In this paper we deal with this problem in a general framework, where weights are supposed to be independent random variables with arbitrary probability distributions and distances are measured by any norm function. Two objective functions are considered to evaluate the performance of any location. The first is defined as the probability of covering all demand points within a given threshold, the second is the threshold for which the probability of covering is bounded from below by a given value. We first present some properties related to the corresponding optimization problems, assuming random weights with both discrete and absolutely continuous probability distributions. For weights with discrete distributions, enumeration techniques can be used to solve the problems. For weights continuously distributed, interval branch and bound algorithms are proposed to solve the problems whatever the probability distributions are. Computational experience using the uniform and the gamma probability distributions is reported.     

A formation problem in plane elasticity

This article discusses modification of the shape of a plane elastic body whose uncontrolled geometric configuration is an annulus, fixed along its interior boundary and free on its outer boundary. The paper discusses the use of radial and circumferential actuators, each of so-called monotropic type, to produce strictly radial deformations of the elastic structure so as to achieve target configurations, or shapes, in a specific class.     

Using geometry to solve the transportation problem in the plane

LetU andV be two sets of points in the plane, where ¦U¦=k,¦V¦=, andn=k+. These two sets of points induce a directed complete bipartite graph in which the points represent nodes and an edge is directed from each node inU to each node in K Each edge is given a cost equal to the distance between the corresponding nodes measured by some metricd on the plane. We consider thetransportation problem on such a graph. We present an 0(n^2,5 logn logN) algorithm, whereN is the magnitude of the largest supply or demand. The algorithm uses some fundamental results of computational geometry and scaling of supplies and demands. The algorithm is valid for the ₁ metric, the ₂ metric, and the metric. The running time for the ₁ and metrics can be improved to 0(n²(logn)³ logN).D. S. Atkinson was supported by the National Science Foundation under Grant CCR90-57481PYI. P. M. Vaidya was supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

On a problem of plane stress

A problem of plane elastic-plastic stress is connected with a varitional problem in an appropriate Hilbert space. Next, the numerical solution of the latter is considered. Finally, the exact and the approximate solutions of a model problem are compared.     

A new heuristic for solving the p-median problem in the plane

This paper presents a new local search for solving the continuous p-median problem in the plane. The basic idea is to first find a good starting solution by overlaying the area containing the set of demand points with a grid and solving heuristically the location problem on this grid. The solution is then used as an initial point for running an improved version of Cooper's well-known alternating local search.     

An optimal parallel algorithm for solving the maximal elements problem in the plane

We describe an O(log(n)) time with O(n) processors optimal algorithm for finding the maximal elements of a set. The model of parallel computation we consider is the CREW-PRAM, i.e. it is the synchronous shared memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing).     

Finding extreme points in three dimensions and solving the post-office problem in the plane

This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ? in h, determine a point of P that is hit first when h is rotated around ?. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved.     

平面应力问题新型广义有限元法

结合广义有限元和理性有限元的优势,针对平面应力问题提出一种新型广义四边形单元.该单元考虑泊松效应,以节点位移自由度约束弹性力学平面应力方程的半解析解,构造单元位移模式的附加项,较准确地反映真实位移场,提高单元的计算精度.推导新型广义单元及其等参单元的形函数公式,设计分片试验和数值算例验证单元的精度.数值算例结果表明：在规则网格和非规则网格下新单元的计算精度均优于传统有限元和广义有限元.新单元具有精度高且易于程序实现的特点,可推广应用到实际工程的结构分析中.     

A novel formulation and solution of the plane elastostatic displacement problem

The displacement problem of elastostatics in two dimensions is formulated in terms of integral equations via the Airy stress function. The integral equations are solved numerically using piecewise constant approximations to the unknown functions. The validity of the formulation is demonstrated by its application to a simple problem with a known solution.     

A necessary condition in the monodromy problem for analytic differential equations on the plane

In this paper we give a very easy to compute necessary condition in the monodromy problem for all singular point of analytic differential systems in the real plane. Our main tool is considering the analytic function, angular speed, and studying its limit through straight lines to the singular point.     

Solving a maximin location problem on the plane with given accuracy

We consider the optimal placement problem in a bounded region on a plane with fixed objects. We specify minimal admissible distances between placed and fixed objects. The optimization criterion is to maximize the minimal weighted distances from placed objects to fixed ones. We propose a quasipolynomial combinatorial algorithm to solve this problem with a given accuracy. We show the results of a computational experiment with the integer programming model and the IBM ILOG CPLEX suite.     

On optimal microstructures for a plane shape optimization problem

The purpose of this article is to discuss some properties of optimal microstructure that are used in the homogenization approach for structural optimization problems involving compliance as the design criterion. The key ingredient for the homogenization method is to allow for microperforated composite materials as admissible designs. Some authors use periodic holes while others rely on optimal microstructures such as the so-called rank-2 layered materials which achieve optimality in the 2-D Hashin-Shtrikman bound. We prove that, in two space dimension, when the eigenvalues of the average stress have opposite signs, there is no optimal periodic microstructure. We also prove in this case that any optimal microstructure is degenerate, like the rank-2 layered material, i.e. it cannot sustain a nonaligned shear stress. When the eigenvalues of the average stress have the same sign, we exhibit higher order layered material that is optimal and not degenerate.     

平面线弹性问题的等几何形状优化方法

介绍具有等几何分析功能的GeoPDEs平台的数据结构和分析流程,针对二维平面形状优化问题,以控制顶点为设计变量,在推导出等几何分析的灵敏度计算公式后,提出基于GeoPDEs平台的灵敏度分析的高效实现方法,并采用移动渐近线法(Method of Moving Asymptotes,MMA)算法进行等几何形状优化.形状优化实例表明该方法收敛速度快,优化结果较理想.     

A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane

We present an optimal O(n) time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane and prove that calculating the optimal value of the objective function requires Θ(nlogn) time.     

Model building and location problem solving in a plane with forbidden gaps

Problems of optimal object location in a plane outside rectangular forbidden gaps are considered. Objects under location are connected with one another and with the objects, located in the same plane. The criteria are the minimization of maximal weighted distance or total cost of the links between objects. A model building procedure of integer linear programming of the problems above for rectangular metric is given. Solution algorithms are briefly described. The outcomes of a numerical experiment are given.     

An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane

We study a bottleneck Steiner tree problem: given a set P={p₁,p₂,…,p_n} of n terminals in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. The problem has applications in the design of wireless communication networks. We give a ratio-1.866 approximation algorithm for the problem.     

AnO(logk)-approximation algorithm for thek minimum spanning tree problem in the plane

Givenn points in the Euclidean plane, we consider the problem of finding the minimum tree spanning anyk points. The problem isNP-hard and we give anO(logk)-approximation algorithm.