Optimizing replacement policy for a cold-standby system with waiting repair times

This paper presents the formulas of the expected long-run cost per unit time for a cold-standby system composed of two identical components with perfect switching. When a component fails, a repairman will be called in to bring the component back to a certain working state. The time to repair is composed of two different time periods: waiting time and real repair time. The waiting time starts from the failure of a component to the start of repair, and the real repair time is the time between the start to repair and the completion of the repair. We also assume that the time to repair can either include only real repair time with a probability p, or include both waiting and real repair times with a probability 1 − p. Special cases are discussed when both working times and real repair times are assumed to be geometric processes, and the waiting time is assumed to be a renewal process. The expected long-run cost per unit time is derived and a numerical example is given to demonstrate the usefulness of the derived expression.     

Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees

In this paper, we present algorithms for enumerating, without repetitions, all triangulations and non-crossing geometric spanning trees on a given set of n points in the plane under edge inclusion constraint (i.e., some edges are required to be included in the graph). We will first extend the lexicographically ordered triangulations introduced by Bespamyatnikh to the edge-constrained case, and then we prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the edge-constrained lexicographically largest triangulation. More specifically, we prove that all edge-constrained triangulations can be transformed to the lexicographically largest triangulation among them by O(n²) greedy flips, i.e., by greedily increasing the lexicographical ordering of the edge list, and a similar result also holds for a set of edge-constrained non-crossing spanning trees. Our enumeration algorithms generate each output triangulation and non-crossing spanning tree in O(loglogn) and O(n²) time, respectively, based on the reverse search technique.     

On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing Edges

A topological graph is called k -quasi-planar if it does not contain k pairwise crossing edges. It is conjectured that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). We provide an affirmative answer to the case k=4.     

On Regular Vertices of the Union of Planar Convex Objects

Let be a collection of n compact convex sets in the plane such that the boundaries of any pair of sets in intersect in at most s points for some constant s≥4. We show that the maximum number of regular vertices (intersection points of two boundaries that intersect twice) on the boundary of the union U of is O ^*(n ^4/3), which improves earlier bounds due to Aronov et al. (Discrete Comput. Geom. 25, 203–220, 2001). The bound is nearly tight in the worst case. In this paper, a bound of the form O ^*(f(n)) means that the actual bound is C _ε f(n)⋅n ^ε for any ε>0, where C _ε is a constant that depends on ε (and generally tends to ∞ as ε decreases to 0). Work by János Pach and Micha Sharir was supported by NSF Grant CCF-05-14079, and by a grant from the U.S.–Israeli Binational Science Foundation. Work by Esther Ezra and Micha Sharir was supported by grant 155/05 from the Israel Science Fund and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Work on this paper by the first author has also been supported by an IBM Doctoral Fellowship. A preliminary version of this paper has been presented in Proc. 23nd Annu. ACM Sympos. Comput. Geom., 2007, pp. 220–226. E. Ezra’s current address: Department of Computer Science, Duke University, Durham, NC 27708-0129, USA. E-mail: esther@cs.duke.edu     

Coloring Geometric Range Spaces

We study several coloring problems for geometric range-spaces. In addition to their theoretical interest, some of these problems arise in sensor networks. Given a set of points in ?² or ?³, we want to color them so that every region of a certain family (e.g., every disk containing at least a certain number of points) contains points of many (say, k) different colors. In this paper, we think of the number of colors and the number of points as functions of k. Obviously, for a fixed k using k colors, it is not always possible to ensure that every region containing k points has all colors present. Thus, we introduce two types of relaxations: either we allow the number of colors used to increase to c(k), or we require that the number of points in each region increases to p(k).Symmetrically, given a finite set of regions in ?² or ?³, we want to color them so that every point covered by a sufficiently large number of regions is contained in regions of k different colors. This requires the number of covering regions or the number of allowed colors to be greater than k.The goal of this paper is to bound these two functions for several types of region families, such as halfplanes, halfspaces, disks, and pseudo-disks. This is related to previous results of Pach, Tardos, and Tóth on decompositions of coverings.     

Pixel-by-pixel absolute phase retrieval using three phase-shifted fringe patterns without markers

This paper presents a method that can recover absolute phase pixel by pixel without embedding markers on three phase-shifted fringe patterns, acquiring additional images, or introducing additional hardware component(s). The proposed three-dimensional (3D) absolute shape measurement technique includes the following major steps: (1) segment the measured object into different regions using rough priori knowledge of surface geometry; (2) artificially create phase maps at different z planes using geometric constraints of structured light system; (3) unwrap the phase pixel by pixel for each region by properly referring to the artificially created phase map; and (4) merge unwrapped phases from all regions into a complete absolute phase map for 3D reconstruction. We demonstrate that conventional three-step phase-shifted fringe patterns can be used to create absolute phase map pixel by pixel even for large depth range objects. We have successfully implemented our proposed computational framework to achieve absolute 3D shape measurement at 40 Hz.     

Characterization for stability in planar conductivities

We find a complete characterization for sets of uniformly strongly elliptic and isotropic conductivities with stable recovery in the $L^2$ norm when the data of the Calderón Inverse Conductivity Problem is obtained in the boundary of a disk and the conductivities are constant in a neighborhood of its boundary. To obtain this result, we present minimal a priori assumptions which turn out to be sufficient for sets of conductivities to have stable recovery in a bounded and rough domain. The condition is presented in terms of the integral moduli of continuity of the coefficients involved and their ellipticity bound as conjectured by Alessandrini in his 2007 paper, giving explicit quantitative control for every pair of conductivities.     

Refined geometric realization of a quantum group and Lusztig’s symmetries

In this paper, we shall give a refinement of the geometric realization of Lusztig’s algebra f given by Lusztig. This realization gives a geometric interpretation of the decomposition of f. As an application, we shall give geometric realizations of Lusztig’s symmetries on the whole quantum group.     

Fourier phase retrieval with a single mask by Douglas–Rachford algorithms

The Fourier-domain Douglas–Rachford (FDR) algorithm is analyzed for phase retrieval with a single random mask. Since the uniqueness of phase retrieval solution requires more than a single oversampled coded diffraction pattern, the extra information is imposed in either of the following forms: 1) the sector condition on the object; 2) another oversampled diffraction pattern, coded or uncoded.For both settings, the uniqueness of projected fixed point is proved and for setting 2) the local, geometric convergence is derived with a rate given by a spectral gap condition. Numerical experiments demonstrate global, power-law convergence of FDR from arbitrary initialization for both settings as well as for 3 or more coded diffraction patterns without oversampling. In practice, the geometric convergence can be recovered from the power-law regime by a simple projection trick, resulting in highly accurate reconstruction from generic initialization.     

土壤中汞与砷分析的热分解浸提前处理方法探讨

采用热分解浸提法处理土壤,以氢化物-原子荧光光谱法测定汞和砷的含量。研究了浸提时间、水浴温度、共存元素对测定结果的影响,对比测定国家级土壤标准物质以及考核样品中汞和砷的含量,其结果与土壤标准物质推荐值相吻合,回收率94.23%—102.73%。用该方法测试了耕地土壤样品中汞和砷的含量,结果表明,该方法简便、快速、准确,适用于实验室常规分析。