Because mechanical operations are performed only up to a certain precision, the geometry of parts involved in real-life products is never known precisely. But if tolerance models for specifying acceptable variations have received a substantial attention, operations on toleranced objects have not been studied extensively. That is the reason why we address in this paper the computation of the union and the intersection of toleranced simple polygons, under a simple and already known tolerance model. First, we provide a practical and efficient algorithm that stores in an implicit data structure the information necessary to answer a request for specific values of the tolerances without performing a computation from scratch. If the polygons are of sizes m and n, and s is the number of intersections between edges occurring for all the combinations of tolerance values, the preprocessed data structure takes O(s) space and the algorithm that computes a union/intersection from it takes O((n + m)log s + k' + k log k) time, where k is the number of vertices of the union/intersection and k ≤ k' ≤ s. Although the algorithm is not output sensitive, we show that the expectations of k and k' remain within a constant factor τ, a function of the input geometry. Second, we define and study the stability of union or intersection features. Third, we list interesting applications of the algorithms related to feasibility of assembly and assembly sequencing of real assemblies.

We develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM) in PV1 + dWPHP(PV).

In Hoare's (1961) original version of the algorithm  the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question.Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergencein distribution of the number of comparisons required and obtain a simple explicit result for the limitingaverage performance of the median-of-three version.

We obtain bounds for the distribution of the number of comparisons needed by Hoare's randomized selection algorithm FIND and give a new proof for Grübel and Rösler's (1996) result on the convergence of this distribution. Our approach is based on the construction and analysis of a suitable associated Markov chain. Some numerical results for the quantiles of the limit distributions are included, leading for example to the statement that, for a set S with n elements and n large, FIND will need with probability 0.9 about 4.72 x n comparisons to find the median of S.

Simulated annealing is a randomized algorithm which has been proposed for finding globally optimum least-cost configurations in large NP-complete problems with cost functions which may have many local minima. A theoretical analysis of simulated annealing based on its precise model, a time-inhomogeneous Markov chain, is presented. An annealing schedule is given for which the Markov chain is strongly ergodic and the algorithm converges to a global optimum. The finite-time behavior of simulated annealing is also analyzed and a bound obtained on the departure of the probability distribution of the state at finite time from the optimum. This bound gives an estimate of the rate of convergence and insights into the conditions on the annealing schedule which gives optimum performance.