Fast computation of smallest enclosing circle with center on a query line segment

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).     

Complexity of Weak Bisimilarity and Regularity for BPA and BPP

It is an open problem whether weak bisimilarity is decidable for Basic Process Algebra (BPA) and Basic Parallel Processes (BPP). A PSPACE lower bound for BPA and NP lower bound for BPP have been demonstrated by Stribrna. Mayr achieved recently a result, saying that weak bisimilarity for BPP is Π^p₂-hard. We improve this lower bound to PSPACE, moreover for the restricted class of normed BPP.Weak regularity (finiteness) of BPA and BPP is not known to be decidable either. In the case of BPP there is a Π^p₂-hardness result by Mayr, which we improve to PSPACE. No lower bound has previously been established for BPA. We demonstrate DP-hardness, which in particular implies both NP and co-NP-hardness.In each of the bisimulation/regularity problems we consider also the classes of normed processes.Note: full version of the paper appears as [18].     

On the centers of a language

The center of a language has been defined in [7, 8, 9] as the set of all words which have infinite right completions in the language. In this paper we extend this notion by taking into account also left and two-sided completions. Thus, for any language X, we consider the left center C_l(X), the right center C_r(X) and two different bilateral centers C₁(X) and C₂(X). Some properties of these centers are derived. In particular the main results of the paper give some general conditions under which C₁(X)=C₂(X)and C_r(C_l(X))=C_l(C_r(X)). These conditions deal with ‘strong’ and ‘weak’ iteration properties and ‘periodicity’ of a language.     

The 1-Versus-2 Queries Problem Revisited

The 1-versus-2 queries problem, which has been extensively studied in computational complexity theory, asks in its generality whether every efficient algorithm that makes at most 2 queries to a Σ _k ^p -complete language L _k has an efficient simulation that makes at most 1 query to L _k . We obtain solutions to this problem for hypotheses weaker than previously considered. We prove that:

On closure properties of bounded two-sided error complexity classes

We show that if a complexity classC is closed downward under polynomial-time majority truth-table reductions ( _mtt ^p ), then practically every other polynomial closure property it enjoys is inherited by the corresponding bounded two-sided error class BP[C]. For instance, the Arthur-Merlin game class AM [B1] enjoys practically every closure property of NP. Our main lemma shows that, for any relativizable classD which meets two fairly transparent technical conditions, we haveC ^BP[C] BP[D ^C]. Among our applications, we simplify the proof by Toda [Tol], [To2] that the polynomial hierarchy PH is contained in BP[P]. We also show that relative to a random oracleR, PH ^R is properly contained in P ^R .The first author was supported in part by NSF Grant CCR-9011248 and the second author was supported in part by NSF Grant CCR-89011154.     

Lumped model of a non-linear distributed system by finite element method

The finite element method has been used to find an approximate lumped parameter model of a non-linear distributed parameter system. A one dimensional non-linear dispersion system is considered. The space domain is divided into a finite set of k elements. Each element, has n nodes. Within each element the concentration is represented by C(x,t)^(e) = [N][C] ^T where [N] = [n₁(x),n₂(x), [tdot] n_n(x)] and [C] = [C₁(t),C₂(t), [tdot] C_n(t)]. By using Galerkin's criterion a set of (k × n ? n+ 1) first order differential equations are obtained for C_i(t). These equations are solved by an iterative method. The concepts are illustrated by an example taking five three-node elements in the space domain. The results are compared with those obtained by a finite difference method. It is shown that the finite element method can be used effectively in modelling of a distributed system by a lumped system.     

A second step toward the strong polynomial-time hierarchy

In this paper we discuss the concepts ofimmunity andsimplicity in levels of the relativized Polynomial-time Hierarchy just aboveP. We consider various diagonalization techniques with which oracle sets can be constructed relative to which strong separations between language classes in the first two levels of this hierarchy are established. In particular, we build oracle sets for separation of relativized Σ ₂ ^P from relativizedNP with immunity, of relativized Σ ₂ ^P from relativizedNP with bi-immunity, of relativized Σ ₂ ^P from relativized Δ ₂ ^P with immunity, of relativized Π ₂ ^P from relativized Δ ₂ ^P with immunity, and finally of relativized Σ ₂ ^P from relativized Π ₂ ^P with simplicity.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

Reliable stabilization using a multi-controller configuration

Given a plant P, we consider the problem of designing a pair of controllers C₁ and C₂ such that their sum stabilizes P, and in addition, each of them also stabilizes P should the other one fail. This is referred to as the reliable stabilization problem. It is shown that every strongly stabilizable plant can be reliably stabilized; moreover, one of the two controllers can be specified arbitrarily, subject only to the constraint that it should be stable. The stabilization technique is extended to reliable regulation.     

On recognizing graph properties from adjacency matrices

A conjecture of Aanderaa and Rosenberg [15] motivates this work. We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C(P) = d whenever P(0^d) ≠ P(1^d) and P is invariant under a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) settles this question for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture: at least $\text{v}{}^2\text{16}$ entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.     

Some results on simultaneous stabilization with multiple domains of stability

In this paper, the problem of simultaneous stabilization in the case where each plant has a different domain of stability associated with it is studied. Specifically, it is supposed that one is given plants P₀, P₁,…, P_r together with domains of stability D₀,…, D_r, and the objective is to find a common controller C such that the poles of the closed-loop transfer matrix H(P_i, C) are all inside the corresponding domain of stability D_i, for i = 0,…, r. This formulation of the simultaneous stabilization problem generalizes earlier problem formulations wherein it was assumed that all the domains of stability were the same, and is believed to be a more realistic formulation of the problem of preserving system stability in the event of sensor or actuator failure. In the paper, necessary and sufficient conditions for the existence of a common controller are derived, in the case where one of the domains (say D₀) is a subset of the rest. The case of two plants P₀, P₁ with D₀ a subset of D₁ is studied in great detail, and the following result is established: the two plants can be simultaneously stabilized in the above generalized sense if and only if they can be simultaneously stabilized with respect to the larger of the two regions. More precisely there exists a controller C such that the poles of H(P_i, C) lie inside D_i for i = 0, 1 if and only if there exists a controller such that the poles of bothH(P₀, C) and of H(P₁, C) lie inside the larger region D₁.     

Robust algorithms that locate local extrema of a function of one variable from interval measurement results: A remark

The problem of locating local maxima and minima of a function from approximate measurement results is vital for many physical applications: inspectral analysis, chemical species are identified by locating local maxima of the spectra; inradioastronomy, sources of celestial radio emission, and their subcomponents, are identified by locating local maxima of the measured brightness of the radio sky;elementary particles are identified by locating local maxima of the experimental curves. Since measurements are never absolutely precise, as a result of the measurements, we have aclass of possible functions. If we measuref(x _i ) with interval uncertainty, this class consists of all functionsf for whichf(x _i ) ε [y _i ??, y _i +?], wherey _i are the results of measuringf(x _i ), andε is the measurement accuracy. For this class, in [2], a linear-time algorithm was described. In real life, a measuring instrument can sometimes malfunction, leading to the so-calledoutliers, i.e., measurementsy _i that can be way offf(x _i ) (and thus do not restrict the actual valuesf(x _i ) at all). In this paper, we describerobust algorithms, i.e., algorithms that find the number of local extrema in the presence of possible outliers. These algorithms solve an important practical problem, but they are not based on any new mathematical results: they simply use algorithms from [2] and [3].     

The computation of fourth virial coefficients for pairwise-additive spherically symmetric interaction potentials

A method is given for computing the fourth virial coefficient D(T) for a pairwise additive spherically symmetric interaction potential. Taking one of the four interacting particles as origin and using the appropriate co-ordinate transformations in the usual way the ninefold integrals defining D(T) are reduced to sixfold integrals which are then formally reduced to triple integrals by expanding out those Ursell-Mayer functions in the integrals not involving the origin particle as infinite series in Legendre polynomials P_S(cos?), where ? is the angle between the radius vectors of the interacting particles. The coefficients in these expansions are integrals of highly oscillatory functions, especially for large s, and are evaluated using the Chebyshev polynomial expansion for the Ursell-Mayer functions, thus making explicit use of the oscillatory behaviour of P_S(cos?). The triple integrals are evaluated using a nonproduct integration formula of the seventh degree employed earlier in the computation of the thirdh virial coefficient. The values of D(T) computed by the present method have the same qualitative behaviour as the literature values but appear to be more accurate, particularly at lower temperatures.     

An optimal visibility graph algorithm for triangulated simple polygons

LetP be a triangulated simple polygon withn sides. The visibility graph ofP has an edge between every pair of polygon vertices that can be connected by an open segment in the interior ofP. We describe an algorithm that finds the visibility graph ofP inO(m) time, wherem is the number of edges in the visibility graph. Becausem can be as small asO(n), the algorithm improves on the more general visibility algorithms of Asanoet al. [AAGHI] and Welzl [W], which take Θ(n ²) time, and on Suri'sO(m logn) visibility graph algorithm for simple polygons [S].     

On Approximating Polygonal Curves in Two and Three Dimensions

Given a polygonal curve P =[p₁, p₂, . . . , p_n], the polygonal approximation problem considered calls for determining a new curve P′ = [p′₁, p′₂, . . . , p′_m] such that (i) m is significantly smaller than n, (ii) the vertices of P′ are an ordered subset of the vertices of P, and (iii) any line segment [p′_A, p′_{A + 1} of P′ that substitutes a chain [p_B, . . . , p_C] in P is such that for all i where B ≤ i ≤ C, the approximation error of p_i with respect to [p′_A, p′_{A + 1}], according to some specified criterion and metric, is less than a predetermined error tolerance. Using the parallel-strip error criterion, we study the following problems for a curve P in R^d, where d = 2, 3: (i) minimize m for a given error tolerance and (ii) given m, find the curve P′ that has the minimum approximation error over all curves that have at most m vertices. These problems are called the min-# and min-ϵ problems, respectively. For R² and with any one of the L₁, L₂, or L_∞ distance metrics, we give algorithms to solve the min-# problem in O(n²) time and the min-ϵ problem in O(n² log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R³ that is strictly monotone with respect to one of the three axes, we show that if the L₁ and L_∞ metrics are used then the min-# problem can be solved in O(n²) time and the min-ϵ problem can be solved in O(n³) time. If distances are computed using the L₂ metric then the min-# and min-ϵ problems can be solved in O(n³) and O(n³ log n) time, respectively. All of our algorithms exhibit O(n²) space complexity. Finally, we show that if it is not essential to minimize m, simple modifications of our algorithms afford a reduction by a factor of n for both time and space.     

You can (sometimes) tell an image by its cover

For a digital image D let the cover of D be defined by C(D) = Σ_P.Q?Dd(P,Q) where d is the city block distance. Formulas are obtained for C(D) for various shapes including upright line segments, rectangles, isosceles triangles and diamonds. It is shown that certain images can be recognized from their cover values in the presence of additional geometric symmetry conditions.     

The μ-basis of a planar rational curve—properties and computation

A moving line L(x,y;t)=0 is a family of lines with one parameter t in a plane. A moving line L(x,y;t)=0 is said to follow a rational curve P(t) if the point P(t₀) is on the line L(x,y;t₀)=0 for any parameter value t₀. A μ-basis of a rational curve P(t) is a pair of lowest degree moving lines that constitute a basis of the module formed by all the moving lines following P(t), which is the syzygy module of P(t). The study of moving lines, especially the μ-basis, has recently led to an efficient method, called the moving line method, for computing the implicit equation of a rational curve [3 and 6]. In this paper, we present properties and equivalent definitions of a μ-basis of a planar rational curve. Several of these properties and definitions are new, and they help to clarify an earlier definition of the μ-basis [3]. Furthermore, based on some of these newly established properties, an efficient algorithm is presented to compute a μ-basis of a planar rational curve. This algorithm applies vector elimination to the moving line module of P(t), and has O(n²) time complexity, where n is the degree of P(t). We show that the new algorithm is more efficient than the fastest previous algorithm [7].     

Matrix computation of subresultant polynomial remainder sequences in integral domains

We present an improved variant of the matrix-triangularization subresultant prs method [1] for the computation of a greatest common divisor of two polynomialsA andB (of degreesm andn, respectively) along with their polynomial remainder sequence. It is improved in the sense that we obtain complete theoretical results, independent of Van Vleck’s theorem [13] (which is not always true [2, 6]), and, instead of transforming a matrix of order 2·max(m, n) [1], we are now transforming a matrix of orderm+n. An example is also included to clarify the concepts.     

Embedding K-ary Complete Trees into Hypercubes

In this paper, dilated embedding and precise embedding of K-ary complete trees into hypercubes are studied. For dilated embedding, a nearly optimal algorithm is proposed which embeds a K-ary complete tree of height h, T_K(h), into an (h − 1)[log K] + [log (K + 2)]-dimensional hypercube with dilation Max{2, φ(K), φ(K + 2)}. φ(x) = min{λ: Σ^λ_i=0Cⁱ_d ≥ x and d = [log x]}. It is clear that [([log x] + 1)/2] ≤ φ(x) ≤ [log x], for x ≥ 3.) For precise embedding, we show a (K − 1)h + 1-dimensional hypercube is large enough to contain T_K(h) as its subgraph, K ≥ 3.     

Quantum zero-error algorithms cannot be composed

We exhibit two black-box problems, both of which have an efficient quantum algorithm with zero-error, yet whose composition does not have an efficient quantum algorithm with zero-error. This shows that quantum zero-error algorithms cannot be composed. In oracle terms, we give a relativized world where ZQP^ZQP≠ZQP, while classically we always have ZPP^ZPP=ZPP.